Best way to compute a truncated singular value decomposition in java

Question

I want to benchmark the best 2 or 3 libraries to compute a truncated singular value decomposition (SVD), i.e. an SVD where only the k largest singular values are kept. Moreover, I have those constraints :

• It has to be a java library
• My matrices are sparse (around 1% non zero values)
• My matrices are quite big (typically 10k x 5k)
• My matrices can also be larger than high (5k x 10k)

I've encountered quite a large range of libraries, but for instance, with Colt, I don't even know if the SVD algorithm takes into account the fact that my matrix is sparse. Also, I did not find a single library that can directly compute the truncated solution (which is supposed to be much faster). Actually, I'm mostly interested in the approximate matrix obtained from the truncated SVD.

Thanks by advance for your help,

Romain Laroche

Answer 1

I had the exact same problem, and my solution is to:

1. run the SVD with Apache Commons Math on your matrix
2. truncate the diagonal matrix to only keep the top-k singular values
3. truncate the other two matrices by only taking the top-k columns for the first one and top-k rows for last one
4. multiply the three matrices

What you obtain is the truncated SVD of your original matrix.

Below is the full solution, tested with matrices having a few thousands rows/columns.

public static double[][] getTruncatedSVD(double[][] matrix, final int k) {
    SingularValueDecomposition svd = new SingularValueDecomposition(new Array2DRowRealMatrix(matrix));

    double[][] truncatedU = new double[svd.getU().getRowDimension()][k];
    svd.getU().copySubMatrix(0, truncatedU.length - 1, 0, k - 1, truncatedU);

    double[][] truncatedS = new double[k][k];
    svd.getS().copySubMatrix(0, k - 1, 0, k - 1, truncatedS);

    double[][] truncatedVT = new double[k][svd.getVT().getColumnDimension()];
    svd.getVT().copySubMatrix(0, k - 1, 0, truncatedVT[0].length - 1, truncatedVT);

    RealMatrix approximatedSvdMatrix = (new Array2DRowRealMatrix(truncatedU)).multiply(new Array2DRowRealMatrix(truncatedS)).multiply(new Array2DRowRealMatrix(truncatedVT));

    return approximatedSvdMatrix.getData();
}