[50/50] git commit: Merge pull request #315 from rezazadeh/sparsesvd

[ma...@apache.org]

Merge pull request #315 from rezazadeh/sparsesvd

Sparse SVD

# Singular Value Decomposition
Given an *m x n* matrix *A*, compute matrices *U, S, V* such that

*A = U * S * V^T*

There is no restriction on m, but we require n^2 doubles to fit in memory.
Further, n should be less than m.

The decomposition is computed by first computing *A^TA = V S^2 V^T*,
computing svd locally on that (since n x n is small),
from which we recover S and V.
Then we compute U via easy matrix multiplication
as *U =  A * V * S^-1*

Only singular vectors associated with the largest k singular values
If there are k such values, then the dimensions of the return will be:

* *S* is *k x k* and diagonal, holding the singular values on diagonal.
* *U* is *m x k* and satisfies U^T*U = eye(k).
* *V* is *n x k* and satisfies V^TV = eye(k).

All input and output is expected in sparse matrix format, 0-indexed
as tuples of the form ((i,j),value) all in RDDs.

# Testing
Tests included. They test:
- Decomposition promise (A = USV^T)
- For small matrices, output is compared to that of jblas
- Rank 1 matrix test included
- Full Rank matrix test included
- Middle-rank matrix forced via k included

# Example Usage

import org.apache.spark.SparkContext
import org.apache.spark.mllib.linalg.SVD
import org.apache.spark.mllib.linalg.SparseMatrix
import org.apache.spark.mllib.linalg.MatrixyEntry

// Load and parse the data file
val data = sc.textFile("mllib/data/als/test.data").map { line =>
      val parts = line.split(',')
      MatrixEntry(parts(0).toInt, parts(1).toInt, parts(2).toDouble)
}
val m = 4
val n = 4

// recover top 1 singular vector
val decomposed = SVD.sparseSVD(SparseMatrix(data, m, n), 1)

println("singular values = " + decomposed.S.data.toArray.mkString)

# Documentation
Added to docs/mllib-guide.md


Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/d009b17d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/d009b17d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/d009b17d

Branch: refs/heads/master
Commit: d009b17d137edf2f1b9da04254e55fb7455faa3d
Parents: 749f842 85b95d0
Author: Matei Zaharia <ma...@databricks.com>
Authored: Wed Jan 22 14:01:30 2014 -0800
Committer: Matei Zaharia <ma...@databricks.com>
Committed: Wed Jan 22 14:01:30 2014 -0800

----------------------------------------------------------------------
 docs/mllib-guide.md                             |  51 +++++
 .../apache/spark/examples/mllib/SparkSVD.scala  |  59 ++++++
 .../apache/spark/mllib/linalg/MatrixEntry.scala |  27 +++
 .../apache/spark/mllib/linalg/MatrixSVD.scala   |  29 +++
 .../org/apache/spark/mllib/linalg/SVD.scala     | 189 +++++++++++++++++++
 .../spark/mllib/linalg/SparseMatrix.scala       |  30 +++
 .../apache/spark/mllib/linalg/SVDSuite.scala    | 158 ++++++++++++++++
 7 files changed, 543 insertions(+)
----------------------------------------------------------------------