You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ra...@apache.org on 2017/04/26 03:04:59 UTC
[17/29] mahout git commit: Ported Distributed Linear Algebra Pages
Ported Distributed Linear Algebra Pages
Project: http://git-wip-us.apache.org/repos/asf/mahout/repo
Commit: http://git-wip-us.apache.org/repos/asf/mahout/commit/cd830b69
Tree: http://git-wip-us.apache.org/repos/asf/mahout/tree/cd830b69
Diff: http://git-wip-us.apache.org/repos/asf/mahout/diff/cd830b69
Branch: refs/heads/website
Commit: cd830b69bbc31addbf2375d92fcd70ce09c6543e
Parents: 660036e
Author: rawkintrevo <tr...@gmail.com>
Authored: Tue Apr 25 09:36:08 2017 -0500
Committer: rawkintrevo <tr...@gmail.com>
Committed: Tue Apr 25 09:36:08 2017 -0500
----------------------------------------------------------------------
website/README.md | 8 +-
website/_config.yml | 2 +-
.../_includes/themes/mahout2/navbar_docs.html | 16 +-
website/_includes/themes/mahout2/page.html | 24 +++
website/_layouts/doc.html | 0
website/programming_guide/algorithms/d-als.md | 58 ------
website/programming_guide/algorithms/d-qr.md | 58 ------
website/programming_guide/algorithms/d-spca.md | 175 -------------------
website/programming_guide/algorithms/d-ssvd.md | 142 ---------------
.../algorithms/linear-algebra/d-als.md | 58 ++++++
.../algorithms/linear-algebra/d-qr.md | 58 ++++++
.../algorithms/linear-algebra/d-spca.md | 175 +++++++++++++++++++
.../algorithms/linear-algebra/d-ssvd.md | 142 +++++++++++++++
13 files changed, 469 insertions(+), 447 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/README.md
----------------------------------------------------------------------
diff --git a/website/README.md b/website/README.md
index 602084c..5a25be0 100644
--- a/website/README.md
+++ b/website/README.md
@@ -117,8 +117,6 @@ This is a helpful tool for reference http://pikock.github.io/bootstrap-magic/3.0
## Pressing ToDos for Reboot
- [ ] Fill out todo list
-- [ ] Rename Dir to `docs`
-- [ ] copy snapshot of current site to `docs/0.13.0` in svn
-- [ ] "flatten" everything (we shouldn't have a docs folder)
-- [ ] refactor multiple navbars back into one
-
\ No newline at end of file
+- [x] "flatten" everything (we shouldn't have a docs folder)
+- [x] Port Distributed Linear Algebra pages
+- [ ]
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/_config.yml
----------------------------------------------------------------------
diff --git a/website/_config.yml b/website/_config.yml
index aa8a27d..ceb1ad6 100644
--- a/website/_config.yml
+++ b/website/_config.yml
@@ -28,7 +28,7 @@ port: 4000
host: 127.0.0.1
baseurl: "" # does not include hostname
-MAHOUT_VERSION : 0.13.1-SNAPSHOT
+MAHOUT_VERSION : 0.13.1
# The production_url is only used when full-domain names are needed
# such as sitemap.txt
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/_includes/themes/mahout2/navbar_docs.html
----------------------------------------------------------------------
diff --git a/website/_includes/themes/mahout2/navbar_docs.html b/website/_includes/themes/mahout2/navbar_docs.html
index 20abf04..51d84f9 100644
--- a/website/_includes/themes/mahout2/navbar_docs.html
+++ b/website/_includes/themes/mahout2/navbar_docs.html
@@ -32,9 +32,9 @@
<li><a href="{{ BASE_PATH}}/programming_guide/mahout-samsara/faq">Samsara FAQ</a></li>
<li role="separator" class="divider"></li>
<li><span><b>Bindings</b><span></li>
- <li><a href="{{ BASE_PATH}}/distributed/mahout-samsara/spark-bindings">Spark Bindings</a></li>
- <li><a href="{{ BASE_PATH}}/distributed/mahout-samsara/flink-bindings">Flink Bindings</a></li>
- <li><a href="{{ BASE_PATH}}/distributed/mahout-samsara/flink-bindings">H20 Bindings</a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/distributed/mahout-samsara/spark-bindings">Spark Bindings</a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/distributed/mahout-samsara/flink-bindings">Flink Bindings</a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/distributed/mahout-samsara/flink-bindings">H20 Bindings</a></li>
</ul>
</li>
@@ -61,11 +61,11 @@
<li id="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">Algorithms<span class="caret"></span></a>
<ul class="dropdown-menu">
- <li><span><b>Samsara Code</b><span></li>
- <li><a href="{{ BASE_PATH}}/algorithms/samsara/dssvd">Dist SVD</a></li>
- <li><a href="{{ BASE_PATH}}/algorithms/samsara/dspca">Dist PCA</a></li>
- <li><a href="{{ BASE_PATH}}/algorithms/samsara/dqr">Dist QR</a></li>
- <li><a href="{{ BASE_PATH}}/algorithms/samsara/dals">Dist ALS</a></li>
+ <li><span><b> Distributed Linear Algebra</b><span></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/algorithms/linear-algebra/d-ssvd.html">Distributed SVD</a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/algorithms/linear-algebra/d-spca.html">Distributed PCA</a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/algorithms/linear-algebra/d-qr.html">Distributed QR-Decomposition </a></li>
+ <li><a href="{{ BASE_PATH}}/programming_guide/algorithms/linear-algebra/d-als.html">Distributed ALS</a></li>
<li role="separator" class="divider"></li>
<li><span><b>Command Line</b><span></li>
<li><a href="/docs/0.13.0">algo1</a></li>
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/_includes/themes/mahout2/page.html
----------------------------------------------------------------------
diff --git a/website/_includes/themes/mahout2/page.html b/website/_includes/themes/mahout2/page.html
index b0a7525..3227e18 100644
--- a/website/_includes/themes/mahout2/page.html
+++ b/website/_includes/themes/mahout2/page.html
@@ -39,7 +39,31 @@
<!-- atom & rss feed -->
<link href="{{ BASE_PATH }}{{ site.JB.atom_path }}" type="application/atom+xml" rel="alternate" title="Sitewide ATOM Feed">
<link href="{{ BASE_PATH }}{{ site.JB.rss_path }}" type="application/rss+xml" rel="alternate" title="Sitewide RSS Feed">
+ <script type="text/x-mathjax-config">
+ MathJax.Hub.Config({
+ tex2jax: {
+ skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
+ }
+ });
+ MathJax.Hub.Queue(function() {
+ var all = MathJax.Hub.getAllJax(), i;
+ for(i = 0; i < all.length; i += 1) {
+ all[i].SourceElement().parentNode.className += ' has-jax';
+ }
+ });
+ </script>
+ <script type="text/javascript">
+ var mathjax = document.createElement('script');
+ mathjax.type = 'text/javascript';
+ mathjax.async = true;
+ mathjax.src = ('https:' == document.location.protocol) ?
+ 'https://c328740.ssl.cf1.rackcdn.com/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML' :
+ 'http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML';
+
+ var s = document.getElementsByTagName('script')[0];
+ s.parentNode.insertBefore(mathjax, s);
+ </script>
</head>
<body>
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/_layouts/doc.html
----------------------------------------------------------------------
diff --git a/website/_layouts/doc.html b/website/_layouts/doc.html
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/d-als.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/d-als.md b/website/programming_guide/algorithms/d-als.md
deleted file mode 100644
index ba06ceb..0000000
--- a/website/programming_guide/algorithms/d-als.md
+++ /dev/null
@@ -1,58 +0,0 @@
----
-layout: mahoutdoc
-title: Mahout Samsara Distributed ALS
-theme:
- name: mahout2
----
-# Distributed Cholesky QR
-
-
-## Intro
-
-Mahout has a distributed implementation of QR decomposition for tall thin matricies[1].
-
-## Algorithm
-
-For the classic QR decomposition of the form `\(\mathbf{A}=\mathbf{QR},\mathbf{A}\in\mathbb{R}^{m\times n}\)` a distributed version is fairly easily achieved if `\(\mathbf{A}\)` is tall and thin such that `\(\mathbf{A}^{\top}\mathbf{A}\)` fits in memory, i.e. *m* is large but *n* < ~5000 Under such circumstances, only `\(\mathbf{A}\)` and `\(\mathbf{Q}\)` are distributed matricies and `\(\mathbf{A^{\top}A}\)` and `\(\mathbf{R}\)` are in-core products. We just compute the in-core version of the Cholesky decomposition in the form of `\(\mathbf{LL}^{\top}= \mathbf{A}^{\top}\mathbf{A}\)`. After that we take `\(\mathbf{R}= \mathbf{L}^{\top}\)` and `\(\mathbf{Q}=\mathbf{A}\left(\mathbf{L}^{\top}\right)^{-1}\)`. The latter is easily achieved by multiplying each verticle block of `\(\mathbf{A}\)` by `\(\left(\mathbf{L}^{\top}\right)^{-1}\)`. (There is no actual matrix inversion happening).
-
-
-
-## Implementation
-
-Mahout `dqrThin(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
-
- def dqrThin[K: ClassTag](A: DrmLike[K], checkRankDeficiency: Boolean = true): (DrmLike[K], Matrix) = {
- if (drmA.ncol > 5000)
- log.warn("A is too fat. A'A must fit in memory and easily broadcasted.")
- implicit val ctx = drmA.context
- val AtA = (drmA.t %*% drmA).checkpoint()
- val inCoreAtA = AtA.collect
- val ch = chol(inCoreAtA)
- val inCoreR = (ch.getL cloned) t
- if (checkRankDeficiency && !ch.isPositiveDefinite)
- throw new IllegalArgumentException("R is rank-deficient.")
- val bcastAtA = sc.broadcast(inCoreAtA)
- val Q = A.mapBlock() {
- case (keys, block) => keys -> chol(bcastAtA).solveRight(block)
- }
- Q -> inCoreR
- }
-
-
-## Usage
-
-The scala `dqrThin(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
-
- import org.apache.mahout.math._
- import decompositions._
- import drm._
-
- val(drmQ, inCoreR) = dqrThin(drma)
-
-
-## References
-
-[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
-
-[2]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
-
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/d-qr.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/d-qr.md b/website/programming_guide/algorithms/d-qr.md
deleted file mode 100644
index 73aa2f3..0000000
--- a/website/programming_guide/algorithms/d-qr.md
+++ /dev/null
@@ -1,58 +0,0 @@
----
-layout: mahoutdoc
-title: Mahout Samsara DQR
-theme:
- name: mahout2
----
-# Distributed Cholesky QR
-
-
-## Intro
-
-Mahout has a distributed implementation of QR decomposition for tall thin matrices[1].
-
-## Algorithm
-
-For the classic QR decomposition of the form `\(\mathbf{A}=\mathbf{QR},\mathbf{A}\in\mathbb{R}^{m\times n}\)` a distributed version is fairly easily achieved if `\(\mathbf{A}\)` is tall and thin such that `\(\mathbf{A}^{\top}\mathbf{A}\)` fits in memory, i.e. *m* is large but *n* < ~5000 Under such circumstances, only `\(\mathbf{A}\)` and `\(\mathbf{Q}\)` are distributed matrices and `\(\mathbf{A^{\top}A}\)` and `\(\mathbf{R}\)` are in-core products. We just compute the in-core version of the Cholesky decomposition in the form of `\(\mathbf{LL}^{\top}= \mathbf{A}^{\top}\mathbf{A}\)`. After that we take `\(\mathbf{R}= \mathbf{L}^{\top}\)` and `\(\mathbf{Q}=\mathbf{A}\left(\mathbf{L}^{\top}\right)^{-1}\)`. The latter is easily achieved by multiplying each vertical block of `\(\mathbf{A}\)` by `\(\left(\mathbf{L}^{\top}\right)^{-1}\)`. (There is no actual matrix inversion happening).
-
-
-
-## Implementation
-
-Mahout `dqrThin(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
-
- def dqrThin[K: ClassTag](A: DrmLike[K], checkRankDeficiency: Boolean = true): (DrmLike[K], Matrix) = {
- if (drmA.ncol > 5000)
- log.warn("A is too fat. A'A must fit in memory and easily broadcasted.")
- implicit val ctx = drmA.context
- val AtA = (drmA.t %*% drmA).checkpoint()
- val inCoreAtA = AtA.collect
- val ch = chol(inCoreAtA)
- val inCoreR = (ch.getL cloned) t
- if (checkRankDeficiency && !ch.isPositiveDefinite)
- throw new IllegalArgumentException("R is rank-deficient.")
- val bcastAtA = sc.broadcast(inCoreAtA)
- val Q = A.mapBlock() {
- case (keys, block) => keys -> chol(bcastAtA).solveRight(block)
- }
- Q -> inCoreR
- }
-
-
-## Usage
-
-The scala `dqrThin(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
-
- import org.apache.mahout.math._
- import decompositions._
- import drm._
-
- val(drmQ, inCoreR) = dqrThin(drma)
-
-
-## References
-
-[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
-
-[2]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
-
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/d-spca.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/d-spca.md b/website/programming_guide/algorithms/d-spca.md
deleted file mode 100644
index c0026b4..0000000
--- a/website/programming_guide/algorithms/d-spca.md
+++ /dev/null
@@ -1,175 +0,0 @@
----
-layout: mahoutdoc
-title: Mahout Samsara Dist Sto PCA
-theme:
- name: mahout2
----
-# Distributed Stochastic PCA
-
-
-## Intro
-
-Mahout has a distributed implementation of Stochastic PCA[1]. This algorithm computes the exact equivalent of Mahout's dssvd(`\(\mathbf{A-1\mu^\top}\)`) by modifying the `dssvd` algorithm so as to avoid forming `\(\mathbf{A-1\mu^\top}\)`, which would densify a sparse input. Thus, it is suitable for work with both dense and sparse inputs.
-
-## Algorithm
-
-Given an *m* `\(\times\)` *n* matrix `\(\mathbf{A}\)`, a target rank *k*, and an oversampling parameter *p*, this procedure computes a *k*-rank PCA by finding the unknowns in `\(\mathbf{A\u22121\mu^\top \approx U\Sigma V^\top}\)`:
-
-1. Create seed for random *n* `\(\times\)` *(k+p)* matrix `\(\Omega\)`.
-2. `\(\mathbf{s_\Omega \leftarrow \Omega^\top \mu}\)`.
-3. `\(\mathbf{Y_0 \leftarrow A\Omega \u2212 1 {s_\Omega}^\top, Y \in \mathbb{R}^{m\times(k+p)}}\)`.
-4. Column-orthonormalize `\(\mathbf{Y_0} \rightarrow \mathbf{Q}\)` by computing thin decomposition `\(\mathbf{Y_0} = \mathbf{QR}\)`. Also, `\(\mathbf{Q}\in\mathbb{R}^{m\times(k+p)}, \mathbf{R}\in\mathbb{R}^{(k+p)\times(k+p)}\)`.
-5. `\(\mathbf{s_Q \leftarrow Q^\top 1}\)`.
-6. `\(\mathbf{B_0 \leftarrow Q^\top A: B \in \mathbb{R}^{(k+p)\times n}}\)`.
-7. `\(\mathbf{s_B \leftarrow {B_0}^\top \mu}\)`.
-8. For *i* in 1..*q* repeat (power iterations):
- - For *j* in 1..*n* apply `\(\mathbf{(B_{i\u22121})_{\u2217j} \leftarrow (B_{i\u22121})_{\u2217j}\u2212\mu_j s_Q}\)`.
- - `\(\mathbf{Y_i \leftarrow A{B_{i\u22121}}^\top\u22121(s_B\u2212\mu^\top \mu s_Q)^\top}\)`.
- - Column-orthonormalize `\(\mathbf{Y_i} \rightarrow \mathbf{Q}\)` by computing thin decomposition `\(\mathbf{Y_i = QR}\)`.
- - `\(\mathbf{s_Q \leftarrow Q^\top 1}\)`.
- - `\(\mathbf{B_i \leftarrow Q^\top A}\)`.
- - `\(\mathbf{s_B \leftarrow {B_i}^\top \mu}\)`.
-9. Let `\(\mathbf{C \triangleq s_Q {s_B}^\top}\)`. `\(\mathbf{M \leftarrow B_q {B_q}^\top \u2212 C \u2212 C^\top + \mu^\top \mu s_Q {s_Q}^\top}\)`.
-10. Compute an eigensolution of the small symmetric `\(\mathbf{M = \hat{U} \Lambda \hat{U}^\top: M \in \mathbb{R}^{(k+p)\times(k+p)}}\)`.
-11. The singular values `\(\Sigma = \Lambda^{\circ 0.5}\)`, or, in other words, `\(\mathbf{\sigma_i= \sqrt{\lambda_i}}\)`.
-12. If needed, compute `\(\mathbf{U = Q\hat{U}}\)`.
-13. If needed, compute `\(\mathbf{V = B^\top \hat{U} \Sigma^{\u22121}}\)`.
-14. If needed, items converted to the PCA space can be computed as `\(\mathbf{U\Sigma}\)`.
-
-## Implementation
-
-Mahout `dspca(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
-
- def dspca[K](drmA: DrmLike[K], k: Int, p: Int = 15, q: Int = 0):
- (DrmLike[K], DrmLike[Int], Vector) = {
-
- // Some mapBlock() calls need it
- implicit val ktag = drmA.keyClassTag
-
- val drmAcp = drmA.checkpoint()
- implicit val ctx = drmAcp.context
-
- val m = drmAcp.nrow
- val n = drmAcp.ncol
- assert(k <= (m min n), "k cannot be greater than smaller of m, n.")
- val pfxed = safeToNonNegInt((m min n) - k min p)
-
- // Actual decomposition rank
- val r = k + pfxed
-
- // Dataset mean
- val mu = drmAcp.colMeans
-
- val mtm = mu dot mu
-
- // We represent Omega by its seed.
- val omegaSeed = RandomUtils.getRandom().nextInt()
- val omega = Matrices.symmetricUniformView(n, r, omegaSeed)
-
- // This done in front in a single-threaded fashion for now. Even though it doesn't require any
- // memory beyond that is required to keep xi around, it still might be parallelized to backs
- // for significantly big n and r. TODO
- val s_o = omega.t %*% mu
-
- val bcastS_o = drmBroadcast(s_o)
- val bcastMu = drmBroadcast(mu)
-
- var drmY = drmAcp.mapBlock(ncol = r) {
- case (keys, blockA) \u21d2
- val s_o:Vector = bcastS_o
- val blockY = blockA %*% Matrices.symmetricUniformView(n, r, omegaSeed)
- for (row \u2190 0 until blockY.nrow) blockY(row, ::) -= s_o
- keys \u2192 blockY
- }
- // Checkpoint Y
- .checkpoint()
-
- var drmQ = dqrThin(drmY, checkRankDeficiency = false)._1.checkpoint()
-
- var s_q = drmQ.colSums()
- var bcastVarS_q = drmBroadcast(s_q)
-
- // This actually should be optimized as identically partitioned map-side A'B since A and Q should
- // still be identically partitioned.
- var drmBt = (drmAcp.t %*% drmQ).checkpoint()
-
- var s_b = (drmBt.t %*% mu).collect(::, 0)
- var bcastVarS_b = drmBroadcast(s_b)
-
- for (i \u2190 0 until q) {
-
- // These closures don't seem to live well with outside-scope vars. This doesn't record closure
- // attributes correctly. So we create additional set of vals for broadcast vars to properly
- // create readonly closure attributes in this very scope.
- val bcastS_q = bcastVarS_q
- val bcastMuInner = bcastMu
-
- // Fix Bt as B' -= xi cross s_q
- drmBt = drmBt.mapBlock() {
- case (keys, block) \u21d2
- val s_q: Vector = bcastS_q
- val mu: Vector = bcastMuInner
- keys.zipWithIndex.foreach {
- case (key, idx) \u21d2 block(idx, ::) -= s_q * mu(key)
- }
- keys \u2192 block
- }
-
- drmY.uncache()
- drmQ.uncache()
-
- val bCastSt_b = drmBroadcast(s_b -=: mtm * s_q)
-
- drmY = (drmAcp %*% drmBt)
- // Fix Y by subtracting st_b from each row of the AB'
- .mapBlock() {
- case (keys, block) \u21d2
- val st_b: Vector = bCastSt_b
- block := { (_, c, v) \u21d2 v - st_b(c) }
- keys \u2192 block
- }
- // Checkpoint Y
- .checkpoint()
-
- drmQ = dqrThin(drmY, checkRankDeficiency = false)._1.checkpoint()
-
- s_q = drmQ.colSums()
- bcastVarS_q = drmBroadcast(s_q)
-
- // This on the other hand should be inner-join-and-map A'B optimization since A and Q_i are not
- // identically partitioned anymore.
- drmBt = (drmAcp.t %*% drmQ).checkpoint()
-
- s_b = (drmBt.t %*% mu).collect(::, 0)
- bcastVarS_b = drmBroadcast(s_b)
- }
-
- val c = s_q cross s_b
- val inCoreBBt = (drmBt.t %*% drmBt).checkpoint(CacheHint.NONE).collect -=:
- c -=: c.t +=: mtm *=: (s_q cross s_q)
- val (inCoreUHat, d) = eigen(inCoreBBt)
- val s = d.sqrt
-
- // Since neither drmU nor drmV are actually computed until actually used, we don't need the flags
- // instructing compute (or not compute) either of the U,V outputs anymore. Neat, isn't it?
- val drmU = drmQ %*% inCoreUHat
- val drmV = drmBt %*% (inCoreUHat %*% diagv(1 / s))
-
- (drmU(::, 0 until k), drmV(::, 0 until k), s(0 until k))
- }
-
-## Usage
-
-The scala `dspca(...)` method can easily be called in any Spark, Flink, or H2O application built with the `math-scala` library and the corresponding `Spark`, `Flink`, or `H2O` engine module as follows:
-
- import org.apache.mahout.math._
- import decompositions._
- import drm._
-
- val (drmU, drmV, s) = dspca(drmA, k=200, q=1)
-
-Note the parameter is optional and its default value is zero.
-
-## References
-
-[1]: Lyubimov and Palumbo, ["Apache Mahout: Beyond MapReduce; Distributed Algorithm Design"](https://www.amazon.com/Apache-Mahout-MapReduce-Dmitriy-Lyubimov/dp/1523775785)
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/d-ssvd.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/d-ssvd.md b/website/programming_guide/algorithms/d-ssvd.md
deleted file mode 100644
index 71cd977..0000000
--- a/website/programming_guide/algorithms/d-ssvd.md
+++ /dev/null
@@ -1,142 +0,0 @@
----
-layout: mahoutdoc
-title: Mahout Samsara DSSVD
-theme:
- name: mahout2
----
-# Distributed Stochastic Singular Value Decomposition
-
-
-## Intro
-
-Mahout has a distributed implementation of Stochastic Singular Value Decomposition [1] using the parallelization strategy comprehensively defined in Nathan Halko's dissertation ["Randomized methods for computing low-rank approximations of matrices"](http://amath.colorado.edu/faculty/martinss/Pubs/2012_halko_dissertation.pdf) [2].
-
-## Modified SSVD Algorithm
-
-Given an `\(m\times n\)`
-matrix `\(\mathbf{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\approx U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\)`:
-
- 1. 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 [Halko, Martinsson, Tropp].
-
- 2. `\(\mathbf{Y=A\boldsymbol{\Omega}},\,\mathbf{Y}\in\mathbb{R}^{m\times\left(k+p\right)}\)`
-
- 3. 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)}\)`; denoted as `\(\mathbf{Q}=\mbox{qr}\left(\mathbf{Y}\right).\mathbf{Q}\)`
-
- 4. `\(\mathbf{B}_{0}=\mathbf{Q}^{\top}\mathbf{A}:\,\,\mathbf{B}\in\mathbb{R}^{\left(k+p\right)\times n}\)`.
-
- 5. If `\(q>0\)`
- repeat: for `\(i=1..q\)`:
- `\(\mathbf{B}_{i}^{\top}=\mathbf{A}^{\top}\mbox{qr}\left(\mathbf{A}\mathbf{B}_{i-1}^{\top}\right).\mathbf{Q}\)`
- (power iterations step).
-
- 6. Compute Eigensolution of a small Hermitian `\(\mathbf{B}_{q}\mathbf{B}_{q}^{\top}=\mathbf{\hat{U}}\boldsymbol{\Lambda}\mathbf{\hat{U}}^{\top}\)`,
- `\(\mathbf{B}_{q}\mathbf{B}_{q}^{\top}\in\mathbb{R}^{\left(k+p\right)\times\left(k+p\right)}\)`.
-
- 7. Singular values `\(\mathbf{\boldsymbol{\Sigma}}=\boldsymbol{\Lambda}^{0.5}\)`,
- or, in other words, `\(s_{i}=\sqrt{\sigma_{i}}\)`.
-
- 8. If needed, compute `\(\mathbf{U}=\mathbf{Q}\hat{\mathbf{U}}\)`.
-
- 9. 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}\)`.
-
-
-
-
-## Implementation
-
-Mahout `dssvd(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
-
- def dssvd[K: ClassTag](drmA: DrmLike[K], k: Int, p: Int = 15, q: Int = 0):
- (DrmLike[K], DrmLike[Int], Vector) = {
-
- val drmAcp = drmA.checkpoint()
-
- val m = drmAcp.nrow
- val n = drmAcp.ncol
- assert(k <= (m min n), "k cannot be greater than smaller of m, n.")
- val pfxed = safeToNonNegInt((m min n) - k min p)
-
- // Actual decomposition rank
- val r = k + pfxed
-
- // We represent Omega by its seed.
- val omegaSeed = RandomUtils.getRandom().nextInt()
-
- // Compute Y = A*Omega.
- var drmY = drmAcp.mapBlock(ncol = r) {
- case (keys, blockA) =>
- val blockY = blockA %*% Matrices.symmetricUniformView(n, r, omegaSeed)
- keys -> blockY
- }
-
- var drmQ = dqrThin(drmY.checkpoint())._1
-
- // Checkpoint Q if last iteration
- if (q == 0) drmQ = drmQ.checkpoint()
-
- var drmBt = drmAcp.t %*% drmQ
-
- // Checkpoint B' if last iteration
- if (q == 0) drmBt = drmBt.checkpoint()
-
- for (i <- 0 until q) {
- drmY = drmAcp %*% drmBt
- drmQ = dqrThin(drmY.checkpoint())._1
-
- // Checkpoint Q if last iteration
- if (i == q - 1) drmQ = drmQ.checkpoint()
-
- drmBt = drmAcp.t %*% drmQ
-
- // Checkpoint B' if last iteration
- if (i == q - 1) drmBt = drmBt.checkpoint()
- }
-
- val (inCoreUHat, d) = eigen(drmBt.t %*% drmBt)
- val s = d.sqrt
-
- // Since neither drmU nor drmV are actually computed until actually used
- // we don't need the flags instructing compute (or not compute) either of the U,V outputs
- val drmU = drmQ %*% inCoreUHat
- val drmV = drmBt %*% (inCoreUHat %*%: diagv(1 /: s))
-
- (drmU(::, 0 until k), drmV(::, 0 until k), s(0 until k))
- }
-
-Note: As a side effect of checkpointing, U and V values are returned as logical operators (i.e. they are neither checkpointed nor computed). Therefore there is no physical work actually done to compute `\(\mathbf{U}\)` or `\(\mathbf{V}\)` until they are used in a subsequent expression.
-
-
-## Usage
-
-The scala `dssvd(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
-
- import org.apache.mahout.math._
- import decompositions._
- import drm._
-
-
- val(drmU, drmV, s) = dssvd(drma, k = 40, q = 1)
-
-
-## References
-
-[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
-
-[2]: [Randomized methods for computing low-rank
-approximations of matrices](http://amath.colorado.edu/faculty/martinss/Pubs/2012_halko_dissertation.pdf)
-
-[2]: [Halko, Martinsson, Tropp](http://arxiv.org/abs/0909.4061)
-
-[3]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
-
-
-
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/linear-algebra/d-als.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/linear-algebra/d-als.md b/website/programming_guide/algorithms/linear-algebra/d-als.md
new file mode 100644
index 0000000..2ef4c83
--- /dev/null
+++ b/website/programming_guide/algorithms/linear-algebra/d-als.md
@@ -0,0 +1,58 @@
+---
+layout: page
+title: Mahout Samsara Distributed ALS
+theme:
+ name: mahout2
+---
+# Distributed Cholesky QR
+
+
+## Intro
+
+Mahout has a distributed implementation of QR decomposition for tall thin matricies[1].
+
+## Algorithm
+
+For the classic QR decomposition of the form `\(\mathbf{A}=\mathbf{QR},\mathbf{A}\in\mathbb{R}^{m\times n}\)` a distributed version is fairly easily achieved if `\(\mathbf{A}\)` is tall and thin such that `\(\mathbf{A}^{\top}\mathbf{A}\)` fits in memory, i.e. *m* is large but *n* < ~5000 Under such circumstances, only `\(\mathbf{A}\)` and `\(\mathbf{Q}\)` are distributed matricies and `\(\mathbf{A^{\top}A}\)` and `\(\mathbf{R}\)` are in-core products. We just compute the in-core version of the Cholesky decomposition in the form of `\(\mathbf{LL}^{\top}= \mathbf{A}^{\top}\mathbf{A}\)`. After that we take `\(\mathbf{R}= \mathbf{L}^{\top}\)` and `\(\mathbf{Q}=\mathbf{A}\left(\mathbf{L}^{\top}\right)^{-1}\)`. The latter is easily achieved by multiplying each verticle block of `\(\mathbf{A}\)` by `\(\left(\mathbf{L}^{\top}\right)^{-1}\)`. (There is no actual matrix inversion happening).
+
+
+
+## Implementation
+
+Mahout `dqrThin(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
+
+ def dqrThin[K: ClassTag](A: DrmLike[K], checkRankDeficiency: Boolean = true): (DrmLike[K], Matrix) = {
+ if (drmA.ncol > 5000)
+ log.warn("A is too fat. A'A must fit in memory and easily broadcasted.")
+ implicit val ctx = drmA.context
+ val AtA = (drmA.t %*% drmA).checkpoint()
+ val inCoreAtA = AtA.collect
+ val ch = chol(inCoreAtA)
+ val inCoreR = (ch.getL cloned) t
+ if (checkRankDeficiency && !ch.isPositiveDefinite)
+ throw new IllegalArgumentException("R is rank-deficient.")
+ val bcastAtA = sc.broadcast(inCoreAtA)
+ val Q = A.mapBlock() {
+ case (keys, block) => keys -> chol(bcastAtA).solveRight(block)
+ }
+ Q -> inCoreR
+ }
+
+
+## Usage
+
+The scala `dqrThin(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
+
+ import org.apache.mahout.math._
+ import decompositions._
+ import drm._
+
+ val(drmQ, inCoreR) = dqrThin(drma)
+
+
+## References
+
+[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
+
+[2]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
+
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/linear-algebra/d-qr.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/linear-algebra/d-qr.md b/website/programming_guide/algorithms/linear-algebra/d-qr.md
new file mode 100644
index 0000000..52074e6
--- /dev/null
+++ b/website/programming_guide/algorithms/linear-algebra/d-qr.md
@@ -0,0 +1,58 @@
+---
+layout: page
+title: Mahout Samsara DQR
+theme:
+ name: mahout2
+---
+# Distributed Cholesky QR
+
+
+## Intro
+
+Mahout has a distributed implementation of QR decomposition for tall thin matrices[1].
+
+## Algorithm
+
+For the classic QR decomposition of the form `\(\mathbf{A}=\mathbf{QR},\mathbf{A}\in\mathbb{R}^{m\times n}\)` a distributed version is fairly easily achieved if `\(\mathbf{A}\)` is tall and thin such that `\(\mathbf{A}^{\top}\mathbf{A}\)` fits in memory, i.e. *m* is large but *n* < ~5000 Under such circumstances, only `\(\mathbf{A}\)` and `\(\mathbf{Q}\)` are distributed matrices and `\(\mathbf{A^{\top}A}\)` and `\(\mathbf{R}\)` are in-core products. We just compute the in-core version of the Cholesky decomposition in the form of `\(\mathbf{LL}^{\top}= \mathbf{A}^{\top}\mathbf{A}\)`. After that we take `\(\mathbf{R}= \mathbf{L}^{\top}\)` and `\(\mathbf{Q}=\mathbf{A}\left(\mathbf{L}^{\top}\right)^{-1}\)`. The latter is easily achieved by multiplying each vertical block of `\(\mathbf{A}\)` by `\(\left(\mathbf{L}^{\top}\right)^{-1}\)`. (There is no actual matrix inversion happening).
+
+
+
+## Implementation
+
+Mahout `dqrThin(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
+
+ def dqrThin[K: ClassTag](A: DrmLike[K], checkRankDeficiency: Boolean = true): (DrmLike[K], Matrix) = {
+ if (drmA.ncol > 5000)
+ log.warn("A is too fat. A'A must fit in memory and easily broadcasted.")
+ implicit val ctx = drmA.context
+ val AtA = (drmA.t %*% drmA).checkpoint()
+ val inCoreAtA = AtA.collect
+ val ch = chol(inCoreAtA)
+ val inCoreR = (ch.getL cloned) t
+ if (checkRankDeficiency && !ch.isPositiveDefinite)
+ throw new IllegalArgumentException("R is rank-deficient.")
+ val bcastAtA = sc.broadcast(inCoreAtA)
+ val Q = A.mapBlock() {
+ case (keys, block) => keys -> chol(bcastAtA).solveRight(block)
+ }
+ Q -> inCoreR
+ }
+
+
+## Usage
+
+The scala `dqrThin(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
+
+ import org.apache.mahout.math._
+ import decompositions._
+ import drm._
+
+ val(drmQ, inCoreR) = dqrThin(drma)
+
+
+## References
+
+[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
+
+[2]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
+
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/linear-algebra/d-spca.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/linear-algebra/d-spca.md b/website/programming_guide/algorithms/linear-algebra/d-spca.md
new file mode 100644
index 0000000..f827908
--- /dev/null
+++ b/website/programming_guide/algorithms/linear-algebra/d-spca.md
@@ -0,0 +1,175 @@
+---
+layout: page
+title: Mahout-Samsara Distributed Stochastic PCA
+theme:
+ name: mahout2
+---
+# Distributed Stochastic PCA
+
+
+## Intro
+
+Mahout has a distributed implementation of Stochastic PCA[1]. This algorithm computes the exact equivalent of Mahout's dssvd(`\(\mathbf{A-1\mu^\top}\)`) by modifying the `dssvd` algorithm so as to avoid forming `\(\mathbf{A-1\mu^\top}\)`, which would densify a sparse input. Thus, it is suitable for work with both dense and sparse inputs.
+
+## Algorithm
+
+Given an *m* `\(\times\)` *n* matrix `\(\mathbf{A}\)`, a target rank *k*, and an oversampling parameter *p*, this procedure computes a *k*-rank PCA by finding the unknowns in `\(\mathbf{A\u22121\mu^\top \approx U\Sigma V^\top}\)`:
+
+1. Create seed for random *n* `\(\times\)` *(k+p)* matrix `\(\Omega\)`.
+2. `\(\mathbf{s_\Omega \leftarrow \Omega^\top \mu}\)`.
+3. `\(\mathbf{Y_0 \leftarrow A\Omega \u2212 1 {s_\Omega}^\top, Y \in \mathbb{R}^{m\times(k+p)}}\)`.
+4. Column-orthonormalize `\(\mathbf{Y_0} \rightarrow \mathbf{Q}\)` by computing thin decomposition `\(\mathbf{Y_0} = \mathbf{QR}\)`. Also, `\(\mathbf{Q}\in\mathbb{R}^{m\times(k+p)}, \mathbf{R}\in\mathbb{R}^{(k+p)\times(k+p)}\)`.
+5. `\(\mathbf{s_Q \leftarrow Q^\top 1}\)`.
+6. `\(\mathbf{B_0 \leftarrow Q^\top A: B \in \mathbb{R}^{(k+p)\times n}}\)`.
+7. `\(\mathbf{s_B \leftarrow {B_0}^\top \mu}\)`.
+8. For *i* in 1..*q* repeat (power iterations):
+ - For *j* in 1..*n* apply `\(\mathbf{(B_{i\u22121})_{\u2217j} \leftarrow (B_{i\u22121})_{\u2217j}\u2212\mu_j s_Q}\)`.
+ - `\(\mathbf{Y_i \leftarrow A{B_{i\u22121}}^\top\u22121(s_B\u2212\mu^\top \mu s_Q)^\top}\)`.
+ - Column-orthonormalize `\(\mathbf{Y_i} \rightarrow \mathbf{Q}\)` by computing thin decomposition `\(\mathbf{Y_i = QR}\)`.
+ - `\(\mathbf{s_Q \leftarrow Q^\top 1}\)`.
+ - `\(\mathbf{B_i \leftarrow Q^\top A}\)`.
+ - `\(\mathbf{s_B \leftarrow {B_i}^\top \mu}\)`.
+9. Let `\(\mathbf{C \triangleq s_Q {s_B}^\top}\)`. `\(\mathbf{M \leftarrow B_q {B_q}^\top \u2212 C \u2212 C^\top + \mu^\top \mu s_Q {s_Q}^\top}\)`.
+10. Compute an eigensolution of the small symmetric `\(\mathbf{M = \hat{U} \Lambda \hat{U}^\top: M \in \mathbb{R}^{(k+p)\times(k+p)}}\)`.
+11. The singular values `\(\Sigma = \Lambda^{\circ 0.5}\)`, or, in other words, `\(\mathbf{\sigma_i= \sqrt{\lambda_i}}\)`.
+12. If needed, compute `\(\mathbf{U = Q\hat{U}}\)`.
+13. If needed, compute `\(\mathbf{V = B^\top \hat{U} \Sigma^{\u22121}}\)`.
+14. If needed, items converted to the PCA space can be computed as `\(\mathbf{U\Sigma}\)`.
+
+## Implementation
+
+Mahout `dspca(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
+
+ def dspca[K](drmA: DrmLike[K], k: Int, p: Int = 15, q: Int = 0):
+ (DrmLike[K], DrmLike[Int], Vector) = {
+
+ // Some mapBlock() calls need it
+ implicit val ktag = drmA.keyClassTag
+
+ val drmAcp = drmA.checkpoint()
+ implicit val ctx = drmAcp.context
+
+ val m = drmAcp.nrow
+ val n = drmAcp.ncol
+ assert(k <= (m min n), "k cannot be greater than smaller of m, n.")
+ val pfxed = safeToNonNegInt((m min n) - k min p)
+
+ // Actual decomposition rank
+ val r = k + pfxed
+
+ // Dataset mean
+ val mu = drmAcp.colMeans
+
+ val mtm = mu dot mu
+
+ // We represent Omega by its seed.
+ val omegaSeed = RandomUtils.getRandom().nextInt()
+ val omega = Matrices.symmetricUniformView(n, r, omegaSeed)
+
+ // This done in front in a single-threaded fashion for now. Even though it doesn't require any
+ // memory beyond that is required to keep xi around, it still might be parallelized to backs
+ // for significantly big n and r. TODO
+ val s_o = omega.t %*% mu
+
+ val bcastS_o = drmBroadcast(s_o)
+ val bcastMu = drmBroadcast(mu)
+
+ var drmY = drmAcp.mapBlock(ncol = r) {
+ case (keys, blockA) \u21d2
+ val s_o:Vector = bcastS_o
+ val blockY = blockA %*% Matrices.symmetricUniformView(n, r, omegaSeed)
+ for (row \u2190 0 until blockY.nrow) blockY(row, ::) -= s_o
+ keys \u2192 blockY
+ }
+ // Checkpoint Y
+ .checkpoint()
+
+ var drmQ = dqrThin(drmY, checkRankDeficiency = false)._1.checkpoint()
+
+ var s_q = drmQ.colSums()
+ var bcastVarS_q = drmBroadcast(s_q)
+
+ // This actually should be optimized as identically partitioned map-side A'B since A and Q should
+ // still be identically partitioned.
+ var drmBt = (drmAcp.t %*% drmQ).checkpoint()
+
+ var s_b = (drmBt.t %*% mu).collect(::, 0)
+ var bcastVarS_b = drmBroadcast(s_b)
+
+ for (i \u2190 0 until q) {
+
+ // These closures don't seem to live well with outside-scope vars. This doesn't record closure
+ // attributes correctly. So we create additional set of vals for broadcast vars to properly
+ // create readonly closure attributes in this very scope.
+ val bcastS_q = bcastVarS_q
+ val bcastMuInner = bcastMu
+
+ // Fix Bt as B' -= xi cross s_q
+ drmBt = drmBt.mapBlock() {
+ case (keys, block) \u21d2
+ val s_q: Vector = bcastS_q
+ val mu: Vector = bcastMuInner
+ keys.zipWithIndex.foreach {
+ case (key, idx) \u21d2 block(idx, ::) -= s_q * mu(key)
+ }
+ keys \u2192 block
+ }
+
+ drmY.uncache()
+ drmQ.uncache()
+
+ val bCastSt_b = drmBroadcast(s_b -=: mtm * s_q)
+
+ drmY = (drmAcp %*% drmBt)
+ // Fix Y by subtracting st_b from each row of the AB'
+ .mapBlock() {
+ case (keys, block) \u21d2
+ val st_b: Vector = bCastSt_b
+ block := { (_, c, v) \u21d2 v - st_b(c) }
+ keys \u2192 block
+ }
+ // Checkpoint Y
+ .checkpoint()
+
+ drmQ = dqrThin(drmY, checkRankDeficiency = false)._1.checkpoint()
+
+ s_q = drmQ.colSums()
+ bcastVarS_q = drmBroadcast(s_q)
+
+ // This on the other hand should be inner-join-and-map A'B optimization since A and Q_i are not
+ // identically partitioned anymore.
+ drmBt = (drmAcp.t %*% drmQ).checkpoint()
+
+ s_b = (drmBt.t %*% mu).collect(::, 0)
+ bcastVarS_b = drmBroadcast(s_b)
+ }
+
+ val c = s_q cross s_b
+ val inCoreBBt = (drmBt.t %*% drmBt).checkpoint(CacheHint.NONE).collect -=:
+ c -=: c.t +=: mtm *=: (s_q cross s_q)
+ val (inCoreUHat, d) = eigen(inCoreBBt)
+ val s = d.sqrt
+
+ // Since neither drmU nor drmV are actually computed until actually used, we don't need the flags
+ // instructing compute (or not compute) either of the U,V outputs anymore. Neat, isn't it?
+ val drmU = drmQ %*% inCoreUHat
+ val drmV = drmBt %*% (inCoreUHat %*% diagv(1 / s))
+
+ (drmU(::, 0 until k), drmV(::, 0 until k), s(0 until k))
+ }
+
+## Usage
+
+The scala `dspca(...)` method can easily be called in any Spark, Flink, or H2O application built with the `math-scala` library and the corresponding `Spark`, `Flink`, or `H2O` engine module as follows:
+
+ import org.apache.mahout.math._
+ import decompositions._
+ import drm._
+
+ val (drmU, drmV, s) = dspca(drmA, k=200, q=1)
+
+Note the parameter is optional and its default value is zero.
+
+## References
+
+[1]: Lyubimov and Palumbo, ["Apache Mahout: Beyond MapReduce; Distributed Algorithm Design"](https://www.amazon.com/Apache-Mahout-MapReduce-Dmitriy-Lyubimov/dp/1523775785)
http://git-wip-us.apache.org/repos/asf/mahout/blob/cd830b69/website/programming_guide/algorithms/linear-algebra/d-ssvd.md
----------------------------------------------------------------------
diff --git a/website/programming_guide/algorithms/linear-algebra/d-ssvd.md b/website/programming_guide/algorithms/linear-algebra/d-ssvd.md
new file mode 100644
index 0000000..64048e7
--- /dev/null
+++ b/website/programming_guide/algorithms/linear-algebra/d-ssvd.md
@@ -0,0 +1,142 @@
+---
+layout: page
+title: Mahout Samsara DSSVD
+theme:
+ name: mahout2
+---
+# Distributed Stochastic Singular Value Decomposition
+
+
+## Intro
+
+Mahout has a distributed implementation of Stochastic Singular Value Decomposition [1] using the parallelization strategy comprehensively defined in Nathan Halko's dissertation ["Randomized methods for computing low-rank approximations of matrices"](http://amath.colorado.edu/faculty/martinss/Pubs/2012_halko_dissertation.pdf) [2].
+
+## Modified SSVD Algorithm
+
+Given an `\(m\times n\)`
+matrix `\(\mathbf{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\approx U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\)`:
+
+ 1. 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 [Halko, Martinsson, Tropp].
+
+ 2. `\(\mathbf{Y=A\boldsymbol{\Omega}},\,\mathbf{Y}\in\mathbb{R}^{m\times\left(k+p\right)}\)`
+
+ 3. 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)}\)`; denoted as `\(\mathbf{Q}=\mbox{qr}\left(\mathbf{Y}\right).\mathbf{Q}\)`
+
+ 4. `\(\mathbf{B}_{0}=\mathbf{Q}^{\top}\mathbf{A}:\,\,\mathbf{B}\in\mathbb{R}^{\left(k+p\right)\times n}\)`.
+
+ 5. If `\(q>0\)`
+ repeat: for `\(i=1..q\)`:
+ `\(\mathbf{B}_{i}^{\top}=\mathbf{A}^{\top}\mbox{qr}\left(\mathbf{A}\mathbf{B}_{i-1}^{\top}\right).\mathbf{Q}\)`
+ (power iterations step).
+
+ 6. Compute Eigensolution of a small Hermitian `\(\mathbf{B}_{q}\mathbf{B}_{q}^{\top}=\mathbf{\hat{U}}\boldsymbol{\Lambda}\mathbf{\hat{U}}^{\top}\)`,
+ `\(\mathbf{B}_{q}\mathbf{B}_{q}^{\top}\in\mathbb{R}^{\left(k+p\right)\times\left(k+p\right)}\)`.
+
+ 7. Singular values `\(\mathbf{\boldsymbol{\Sigma}}=\boldsymbol{\Lambda}^{0.5}\)`,
+ or, in other words, `\(s_{i}=\sqrt{\sigma_{i}}\)`.
+
+ 8. If needed, compute `\(\mathbf{U}=\mathbf{Q}\hat{\mathbf{U}}\)`.
+
+ 9. 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}\)`.
+
+
+
+
+## Implementation
+
+Mahout `dssvd(...)` is implemented in the mahout `math-scala` algebraic optimizer which translates Mahout's R-like linear algebra operators into a physical plan for both Spark and H2O distributed engines.
+
+ def dssvd[K: ClassTag](drmA: DrmLike[K], k: Int, p: Int = 15, q: Int = 0):
+ (DrmLike[K], DrmLike[Int], Vector) = {
+
+ val drmAcp = drmA.checkpoint()
+
+ val m = drmAcp.nrow
+ val n = drmAcp.ncol
+ assert(k <= (m min n), "k cannot be greater than smaller of m, n.")
+ val pfxed = safeToNonNegInt((m min n) - k min p)
+
+ // Actual decomposition rank
+ val r = k + pfxed
+
+ // We represent Omega by its seed.
+ val omegaSeed = RandomUtils.getRandom().nextInt()
+
+ // Compute Y = A*Omega.
+ var drmY = drmAcp.mapBlock(ncol = r) {
+ case (keys, blockA) =>
+ val blockY = blockA %*% Matrices.symmetricUniformView(n, r, omegaSeed)
+ keys -> blockY
+ }
+
+ var drmQ = dqrThin(drmY.checkpoint())._1
+
+ // Checkpoint Q if last iteration
+ if (q == 0) drmQ = drmQ.checkpoint()
+
+ var drmBt = drmAcp.t %*% drmQ
+
+ // Checkpoint B' if last iteration
+ if (q == 0) drmBt = drmBt.checkpoint()
+
+ for (i <- 0 until q) {
+ drmY = drmAcp %*% drmBt
+ drmQ = dqrThin(drmY.checkpoint())._1
+
+ // Checkpoint Q if last iteration
+ if (i == q - 1) drmQ = drmQ.checkpoint()
+
+ drmBt = drmAcp.t %*% drmQ
+
+ // Checkpoint B' if last iteration
+ if (i == q - 1) drmBt = drmBt.checkpoint()
+ }
+
+ val (inCoreUHat, d) = eigen(drmBt.t %*% drmBt)
+ val s = d.sqrt
+
+ // Since neither drmU nor drmV are actually computed until actually used
+ // we don't need the flags instructing compute (or not compute) either of the U,V outputs
+ val drmU = drmQ %*% inCoreUHat
+ val drmV = drmBt %*% (inCoreUHat %*%: diagv(1 /: s))
+
+ (drmU(::, 0 until k), drmV(::, 0 until k), s(0 until k))
+ }
+
+Note: As a side effect of checkpointing, U and V values are returned as logical operators (i.e. they are neither checkpointed nor computed). Therefore there is no physical work actually done to compute `\(\mathbf{U}\)` or `\(\mathbf{V}\)` until they are used in a subsequent expression.
+
+
+## Usage
+
+The scala `dssvd(...)` method can easily be called in any Spark or H2O application built with the `math-scala` library and the corresponding `Spark` or `H2O` engine module as follows:
+
+ import org.apache.mahout.math._
+ import decompositions._
+ import drm._
+
+
+ val(drmU, drmV, s) = dssvd(drma, k = 40, q = 1)
+
+
+## References
+
+[1]: [Mahout Scala and Mahout Spark Bindings for Linear Algebra Subroutines](http://mahout.apache.org/users/sparkbindings/ScalaSparkBindings.pdf)
+
+[2]: [Randomized methods for computing low-rank
+approximations of matrices](http://amath.colorado.edu/faculty/martinss/Pubs/2012_halko_dissertation.pdf)
+
+[2]: [Halko, Martinsson, Tropp](http://arxiv.org/abs/0909.4061)
+
+[3]: [Mahout Spark and Scala Bindings](http://mahout.apache.org/users/sparkbindings/home.html)
+
+
+