svn commit: r900823 - in /websites/staging/mahout/trunk/content: ./ users/dim-reduction/ssvd.html

[bu...@apache.org]

Author: buildbot
Date: Mon Mar 10 04:26:45 2014
New Revision: 900823

Log:
Staging update by buildbot for mahout

Modified:
    websites/staging/mahout/trunk/content/   (props changed)
    websites/staging/mahout/trunk/content/users/dim-reduction/ssvd.html

Propchange: websites/staging/mahout/trunk/content/
------------------------------------------------------------------------------
--- cms:source-revision (original)
+++ cms:source-revision Mon Mar 10 04:26:45 2014
@@ -1 +1 @@
-1575810
+1575811

Modified: websites/staging/mahout/trunk/content/users/dim-reduction/ssvd.html
==============================================================================
--- websites/staging/mahout/trunk/content/users/dim-reduction/ssvd.html (original)
+++ websites/staging/mahout/trunk/content/users/dim-reduction/ssvd.html Mon Mar 10 04:26:45 2014
@@ -255,34 +255,13 @@ x<span class="o">&lt;-</span> usim <span
 
 <p>and try to compare ssvd.svd(x) and stock svd(x) performance for the same rank k, notice the difference in the running time. Also play with power iterations (qIter) and compare accuracies of standard svd and SSVD.</p>
 <p>Note: numerical stability of R algorithms may differ from that of Mahout's distributed version. We haven't studied accuracy of the R simulation. For study of accuracy of Mahout's version, please refer to Nathan's dissertation as referenced above.</p>
-<h3 id="general-ssvd-algorithm-flow">General SSVD algorithm flow</h3>
-<div>
-Given an \(m\times n\) matrix **A**, a target rank \(k\in\mathbb{N}_{1}\),
-an oversampling parameter \(p\in\mathbb{N}_{1}\), and the number of
-additional power iterations \(q\in\mathbb{N}_{0}\), this procedure
-computes an \(m\times\left(k+p\right)\) SVD \(\mathbf{A=U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\)
-</div>
-
-<p>\begin{enumerate}
-\item Create seed for random $n\times\left(k+p\right)$ matrix $\boldsymbol{\Omega}$.
-The seed defines matrix $\mathbf{\Omega}$ using Gaussian unit vectors
-per one of suggestions in \cite{Martinsson}.
-\item $\mathbf{Y=A\boldsymbol{\Omega}},\,\mathbf{Y}\in\mathbb{R}^{m\times\left(k+p\right)}$.
-\item Column-orthonormalize $\mathbf{Y}\rightarrow\mathbf{Q}$ by computing
-thin decomposition $\mathbf{Y}=\mathbf{Q}\mathbf{R}$. Also, $\mathbf{Q}\in\mathbb{R}^{m\times\left(k+p\right)},\,\mathbf{R}\in\mathbb{R}^{\left(k+p\right)\times\left(k+p\right)}$.
-I denote this as $\mathbf{Q}=\mbox{qr}\left(\mathbf{Y}\right).\mathbf{Q}$.
-\item $\mathbf{B}<em>{0}=\mathbf{Q}^{\top}\mathbf{A}:\,\,\mathbf{B}\in\mathbb{R}^{\left(k+p\right)\times n}$.
-(Another way is $\mathbf{R}^{-1}\mathbf{Y}^{\top}\mathbf{A}$, depending
-on whether we beleive if size of A less than size of Q).
-\item If $q&gt;0$ repeat: for $i=1..q$: $\mathbf{B}</em>{i}^{\top}=\mathbf{A}^{\top}\mbox{qr}\left(\mathbf{A}\mathbf{B}<em>{i-1}^{\top}\right).\mathbf{Q}$
-(power iterations step)
-\item Compute Eigensolution of a small Hermitian $\mathbf{B}</em>{q}\mathbf{B}<em>{q}^{\top}=\mathbf{\hat{U}}\boldsymbol{\Lambda}\mathbf{\hat{U}}^{\top}$.
-$\mathbf{B}</em>{q}\mathbf{B}<em>{q}^{\top}\in\mathbb{R}^{\left(k+p\right)\times\left(k+p\right)}$.
-\item Singular values $\mathbf{\boldsymbol{\Sigma}}=\boldsymbol{\Lambda}^{0.5}$,
-or, in other words, $s</em>{i}=\sqrt{\sigma_{i}}$.
-\item If needed, compute $\mathbf{U}=\mathbf{Q}\hat{\mathbf{U}}$.
-\item If needed, compute $\mathbf{V}=\mathbf{B}_{q}^{\top}\hat{\mathbf{U}}\boldsymbol{\Sigma}^{-1}$.
-Another way is $\mathbf{V}=\mathbf{A}^{\top}\mathbf{U}\boldsymbol{\Sigma}^{-1}$.\end{enumerate}</p>
+<h4 id="modified-ssvd-algorithm">Modified SSVD Algorithm.</h4>
+<p>Given an (m\times n)
+  matrix (\mathbb{A}), a target rank (k\in\mathbb{N}<em>{1})
+ , an oversampling parameter (p\in\mathbb{N}</em>{1})
+ , and the number of additional power iterations (q\in\mathbb{N}_{0})
+ , this procedure computes an (m\times\left(k+p\right))
+  SVD (\mathbf{A\approx U}\boldsymbol{\Sigma}\mathbf{V}^{\top}):</p>
 <script type="text/javascript"
   src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
 </script>