Лучший способ вычислить усеченное разложение по сингулярным значениям в Java

Question

Я хочу сравнить лучшие 2 или 3 библиотеки для вычисления усеченного разложения по сингулярным значениям (SVD), то есть SVD, где хранятся только k самых больших значений в единственном числе. Кроме того, у меня есть эти ограничения:

• Это должна быть библиотека Java
• Мои матрицы разрежены (около 1% ненулевых значений)
• Мои матрицы довольно большие (обычно 10k x 5k)
• Мои матрицы также могут быть больше, чем высокие (5k x 10k)

Я встречал довольно большой спектр библиотек, но, например, с Colt я даже не знаю, учитывает ли алгоритм SVD тот факт, что моя матрица редка. Кроме того, я не нашел ни одной библиотеки, которая могла бы напрямую вычислять усеченное решение (которое должно быть намного быстрее). На самом деле, меня больше всего интересует примерная матрица, полученная из усеченного SVD.

Спасибо заранее за вашу помощь,

Ромен Ларош

Answer 1

У меня была точно такая же проблема, и мое решение:

1. запустите SVD с Apache Commons Math на вашей матрице
2. обрезать диагональную матрицу, чтобы сохранить только топ-сингулярные значения
3. усечь две другие матрицы, взяв только столбцы top- k для первой и строки top- k для последней
4. умножить три матрицы

То, что вы получаете, является усеченным SVD вашей исходной матрицы.

Ниже приведено полное решение, протестированное с матрицами, имеющими несколько тысяч строк / столбцов.

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();
}

Answer 2

Я использовал библиотеку http://math.nist.gov/javanumerics/jama/ которая довольно хороша.