package jsat.linear;

import java.io.Serializable;
import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import static java.lang.Math.*;
import static jsat.linear.RowColumnOps.*;

/**
 * The Singular Value Decomposition (SVD) of a matrix Am,n  = Um,n  Σn,n  VTn,n , 
 * where S is the diagonal matrix of the singular values sorted in descending order and are all non negative. 
 * 
The SVD of a matrix has many practical uses, but is expensive to compute. *

* Implementation adapted from the Public Domain work of JAMA: A Java Matrix Package *
* NOTE: The current implementation has been revised and is now passing all test cases. * However, it is still being tested. Use with awareness that it used to be bugged. * Note left at revision 597 * * @author Edward Raff */ public class SingularValueDecomposition implements Cloneable, Serializable { private static final long serialVersionUID = 1711766946748622002L; private Matrix U, V; /** * Stores the diagonal values of the S matrix, and contains the bidiagonal values of A during initial steps. */ private double[] s; /** * Creates a new SVD of the matrix {@code A} such that A = U Σ VT. The matrix * {@code A} will be modified and used as temp space when computing the SVD. * @param A the matrix to create the SVD of */ public SingularValueDecomposition(Matrix A) { this(A, 100); } /** * Creates a new SVD of the matrix {@code A} such that A = U Σ VT. The matrix * {@code A} will be modified and used as temp space when computing the SVD. * @param A the matrix to create the SVD of * @param maxIterations the maximum number of iterations to perform per singular value till convergence. */ public SingularValueDecomposition(Matrix A, int maxIterations) { //By doing this we get to keep the colum major algo and get row major performance final boolean transposedWord = A.rows() < A.cols(); Matrix AA = transposedWord ? new TransposeView(A) : A; int m = AA.rows(); int n = AA.cols(); int nu = min(m, n); U = new DenseMatrix(m, nu); V = new DenseMatrix(n, n); s = new double[min(m + 1, n)]; double[] e = new double[n]; double[] work = new double[m]; int nct = min(m - 1, n); int nrt = max(0, min(n - 2, m)); bidiagonalize(nct, nrt, m, AA, n, e, work); // Set up the final bidiagonal matrix or order p. int p = min(n, m + 1); if (nct < n) s[nct] = AA.get(nct, nct); if (m < p) s[p - 1] = 0.0; if (nrt + 1 < p) e[nrt] = AA.get(nrt, p - 1); e[p - 1] = 0.0; generateU(nct, nu, m); generateV(n, nrt, e, nu); mainIterationLoop(p, e, n, m, maxIterations); if(transposedWord) { /* * A = U S V' * A' = V S' U' */ Matrix tmp = V; V = U; U = tmp; } } /** * Sets the values for a SVD explicitly. This is not a copy constructor, and * will hold the given values. * * @param U the U matrix of an SVD * @param V the V matrix of an SVD * @param s the singular sorted by magnitude of an SVD */ public SingularValueDecomposition(Matrix U, Matrix V, double[] s) { this.U = U; this.V = V; this.s = s; } private void bidiagonalize(int nct, int nrt, int m, Matrix A, int n, double[] e, double[] work) { for (int k = 0; k < max(nct, nrt); k++) { if (k < nct) { // Compute the transformation for the k-th column and // place the k-th diagonal in s[k]. s[k] = 0; for (int i = k; i < m; i++) s[k] = hypot(s[k], A.get(i, k)); if (s[k] != 0.0) { if (A.get(k, k) < 0.0) s[k] = -s[k]; divCol(A, k, k, m, s[k]); A.increment(k, k, 1.0); } s[k] = -s[k]; } for (int j = k + 1; j < n; j++) { if ((k < nct) & (s[k] != 0.0)) { // Apply the transformation. double t = 0; for (int i = k; i < m; i++) t += A.get(i, k) * A.get(i, j); t = -t / A.get(k, k); for(int i = k; i < m; i++) A.increment(i, j, t*A.get(i, k)); } // Place the k-th row of A into e for the // subsequent calculation of the row transformation. e[j] = A.get(k, j); } if (k < nct) { // Place the transformation in U for subsequent back // multiplication. for (int i = k; i < m; i++) U.set(i, k, A.get(i, k)); } if (k < nrt) { superDiagonalCreation(e, k, n, m, work, A); } } } private int sLength() { return min(U.rows(), V.rows()); } private void superDiagonalCreation(double[] e, int k, int n, int m, double[] work, Matrix A) { // Compute the k-th row transformation and place the // k-th super-diagonal in e[k]. e[k] = 0; for (int i = k + 1; i < n; i++) e[k] = Math.hypot(e[k], e[i]); if (e[k] != 0.0) { if (e[k + 1] < 0.0) e[k] = -e[k]; for (int i = k + 1; i < n; i++) e[i] /= e[k]; e[k + 1] += 1.0; } e[k] = -e[k]; if ((k + 1 < m) & (e[k] != 0.0)) { // Apply the transformation. Arrays.fill(work, k+1, m, 0.0); for (int j = k + 1; j < n; j++) for (int i = k + 1; i < m; i++) work[i] += e[j] * A.get(i, j); for (int j = k + 1; j < n; j++) { double t = -e[j] / e[k + 1]; addMultCol(A, j, k+1, m, t, work); } } // Place the transformation in V for subsequent // back multiplication. for (int i = k + 1; i < n; i++) V.set(i, k, e[i]); } private void generateV(int n, int nrt, double[] e, int nu) { for (int k = n - 1; k >= 0; k--) { if ((k < nrt) & (e[k] != 0.0)) { for (int j = k + 1; j < nu; j++) { double t = 0; for (int i = k + 1; i < n; i++) t += V.get(i, k) * V.get(i, j); t = -t / V.get(k + 1, k); for (int i = k + 1; i < n; i++) V.increment(i, j, t * V.get(i, k)); } } for (int i = 0; i < n; i++) V.set(i, k, 0.0); V.set(k, k, 1.0); } } private void generateU(int nct, int nu, int m) { for (int j = nct; j < nu; j++) { for (int i = 0; i < m; i++) U.set(i, j, 0.0); U.set(j, j, 1.0); } for (int k = nct - 1; k >= 0; k--) { if (s[k] != 0.0) { for (int j = k + 1; j < nu; j++) { double t = 0; for (int i = k; i < m; i++) t += U.get(i, k) * U.get(i, j); t = -t / U.get(k, k); for (int i = k; i < m; i++) U.increment(i, j, t * U.get(i, k)); } for (int i = k; i < m; i++) U.set(i, k, -U.get(i, k)); U.set(k, k, 1.0 + U.get(k, k)); for (int i = 0; i < k - 1; i++) U.set(i, k, 0.0); } else { for (int i = 0; i < m; i++) U.set(i, k, 0.0); U.set(k, k, 1.0); } } } private void mainIterationLoop(int p, double[] e, int n, int m, int maxIterations) { // Main iteration loop for the singular values. int pp = p - 1; int iter = 0; double eps = pow(2.0, -52.0); while (p > 0 && iter < maxIterations) { int k, kase; // This section of the program inspects for // negligible elements in the s and e arrays. On // completion the variables kase and k are set as follows. // kase = 1 if s(p) and e[k-1] are negligible and k

= -1; k--) { if (k == -1) { break; } if (abs(e[k]) <= eps * (abs(s[k]) + abs(s[k + 1]))) { e[k] = 0.0; break; } } if (k == p - 2) { kase = 4; } else { int ks; for (ks = p - 1; ks >= k; ks--) { if (ks == k) break; double t = (ks != p ? abs(e[ks]) : 0.) + (ks != k + 1 ? abs(e[ks - 1]) : 0.); if (abs(s[ks]) <= eps * t) { s[ks] = 0.0; break; } } if (ks == k) { kase = 3; } else if (ks == p - 1) { kase = 1; } else { kase = 2; k = ks; } } k++; // Perform the task indicated by kase. switch (kase) { // Deflate negligible s(p). case 1: { case1(e, p, k, n); } break; // Split at negligible s(k). case 2: { case2(e, k, p, m); } break; case 3: { case3QRStep(p, e, k, n, m); iter++; } break; // Convergence. case 4: { // Make the singular values positive. if (s[k] <= 0.0) { s[k] = (s[k] < 0.0 ? -s[k] : 0.0); multCol(V, k, 0, pp+1, -1); } // Order the singular values. while (k < pp) { if (s[k] >= s[k + 1]) break; double t = s[k]; s[k] = s[k + 1]; s[k + 1] = t; if (k < n - 1) swapCol(V, k, k+1, 0, n); if (k < m - 1) swapCol(U, k, k+1, 0, m); k++; } iter = 0; p--; } break; } } } private void case1(double[] e, int p, int k, int n) { double f = e[p - 2]; e[p - 2] = 0.0; for (int j = p - 2; j >= k; j--) { double t = hypot(s[j], f); double cs = s[j] / t; double sn = f / t; s[j] = t; if (j != k) { f = -sn * e[j - 1]; e[j - 1] = cs * e[j - 1]; } UVCase12Update(V, n, cs, j, sn, p); } } private void case2(double[] e, int k, int p, int m) { double f = e[k - 1]; e[k - 1] = 0.0; for (int j = k; j < p; j++) { double t = hypot(s[j], f); double cs = s[j] / t; double sn = f / t; s[j] = t; f = -sn * e[j]; e[j] = cs * e[j]; UVCase12Update(U, m, cs, j, sn, k); } } private void UVCase12Update(Matrix UV, int m, double cs, int j, double sn, int k) { double t; for (int i = 0; i < m; i++) { t = cs * UV.get(i, j) + sn * UV.get(i, k - 1); UV.set(i, k - 1, -sn * UV.get(i, j) + cs * UV.get(i, k - 1)); UV.set(i, j, t); } } private void case3QRStep(int p, double[] e, int k, int n, int m) { // Calculate the shift. double scale = max(max(max(max( abs(s[p - 1]), abs(s[p - 2])), abs(e[p - 2])), abs(s[k])), abs(e[k])); double sp = s[p - 1] / scale; double spm1 = s[p - 2] / scale; double epm1 = e[p - 2] / scale; double sk = s[k] / scale; double ek = e[k] / scale; double b = ((spm1 + sp) * (spm1 - sp) + epm1 * epm1) / 2.0; double c = (sp * epm1) * (sp * epm1); double shift = 0.0; if ((b != 0.0) | (c != 0.0)) { shift = sqrt(b * b + c); if (b < 0.0) { shift = -shift; } shift = c / (b + shift); } double f = (sk + sp) * (sk - sp) + shift; double g = sk * ek; // Chase zeros. for (int j = k; j < p - 1; j++) { double t = hypot(f, g); double cs = f / t; double sn = g / t; if (j != k) e[j - 1] = t; f = cs * s[j] + sn * e[j]; e[j] = cs * e[j] - sn * s[j]; g = sn * s[j + 1]; s[j + 1] = cs * s[j + 1]; UVCase3Update(V, n, cs, j, sn); t = hypot(f, g); cs = f / t; sn = g / t; s[j] = t; f = cs * e[j] + sn * s[j + 1]; s[j + 1] = -sn * e[j] + cs * s[j + 1]; g = sn * e[j + 1]; e[j + 1] = cs * e[j + 1]; if (j < m - 1) { UVCase3Update(U, m, cs, j, sn); } } e[p - 2] = f; } private void UVCase3Update(Matrix UV, int m, double cs, int j, double sn) { double t; for (int i = 0; i < m; i++) { t = cs * UV.get(i, j) + sn * UV.get(i, j + 1); UV.set(i, j + 1, -sn * UV.get(i, j) + cs * UV.get(i, j + 1)); UV.set(i, j, t); } } /** * Returns the backing matrix U of the SVD. Do not alter this matrix. * @return the matrix U of the SVD */ public Matrix getU() { return U; } /** * Returns the backing matrix V of the SVD. Do not later this matrix. * @return the matrix V of the SVD */ public Matrix getV() { return V; } /** * Returns a copy of the sorted array of the singular values, include the near zero ones. * @return a copy of the sorted array of the singular values, including the near zero ones. */ public double[] getSingularValues() { return Arrays.copyOf(s, sLength()); } /** * Returns the diagonal matrix S such that the SVD product results in the original matrix. The diagonal contains the singular values. * @return a dense diagonal matrix containing the singular values */ public Matrix getS() { Matrix DS = new DenseMatrix(U.rows(), V.rows()); for(int i = 0; i < sLength(); i++) DS.set(i, i, s[i]); return DS; } /** * Returns the 2 norm of the matrix, which is the maximal singular value. * @return the 2 norm of the matrix */ public double getNorm2() { return s[0]; } /** * Returns the condition number of the matrix. The condition number is a positive measure of the numerical * instability of the matrix. The larger the value, the less stable the matrix. For singular matrices, * the result is {@link Double#POSITIVE_INFINITY}. * @return the condition number of the matrix */ public double getCondition() { return getNorm2()/s[sLength()-1]; } private double getDefaultTolerance() { return max(U.rows(), V.rows())*(nextUp(getNorm2())-getNorm2()); } /** * Returns the numerical rank of the matrix. Near zero values will be ignored. * @return the rank of the matrix */ public int getRank() { return getRank(getDefaultTolerance()); } /** * Indicates whether or not the input matrix was of full rank, full * rank matrices are more numerically stable. * * @return true if the matrix was of full tank */ public boolean isFullRank() { return getRank() == sLength(); } /** * Returns the numerical rank of the matrix. Values <= than tol will be ignored. * @param tol the cut of for singular values * @return the rank of the matrix */ public int getRank(double tol) { for(int i = 0; i < sLength(); i++) if(s[i] <= tol) return i; return sLength(); } /** * Returns an array containing the inverse singular values. Near zero values are converted to zero. * @return an array containing the inverse singular values */ public double[] getInverseSingularValues() { return getInverseSingularValues(getDefaultTolerance()); } /** * Returns an array containing the inverse singular values. Values that are <= tol are converted to zero. * @param tol the cut of for singular values * @return an array containing the inverse singular values */ public double[] getInverseSingularValues(double tol) { double[] sInv = Arrays.copyOf(s, sLength()); for(int i = 0; i < sInv.length; i++) if(sInv[i] > tol) sInv[i] = 1.0/sInv[i]; else sInv[i] = 0; return sInv; } /** * Returns the Moore–Penrose pseudo inverse of the matrix. The pseudo inverse for a matrix is unique. If a matrix * is non singular, the pseudo inverse is the inverse. * * @return the pseudo inverse of the matrix */ public Matrix getPseudoInverse() { return getPseudoInverse(getDefaultTolerance()); } /** * Returns the Moore–Penrose pseudo inverse of the matrix. The pseudo inverse for a matrix is unique. If a matrix * is non singular, the pseudo inverse is the inverse. * * @param tol the tolerance for singular values to ignore * @return the pseudo inverse of the matrix */ public Matrix getPseudoInverse(double tol) { Matrix UT = U.transpose(); Matrix.diagMult(DenseVector.toDenseVec(getInverseSingularValues(tol)), UT); return V.multiply(UT); } /** * Computes the pseudo determinant of the matrix, which corresponds to absolute value of * the determinant of the full rank square sub matrix that contains all non zero singular values. * * @return the pseudo determinant. */ public double getPseudoDet() { return getPseudoDet(getDefaultTolerance()); } /** * Computes the pseudo determinant of the matrix, which corresponds to absolute value of * the determinant of the full rank square sub matrix that contains all non singular values > tol. * * @param tol the cut of for singular values * @return the pseudo determinant */ public double getPseudoDet(double tol) { double det = 1; for (double d : s) if (d <= tol) break; else det *= d; return det; } /** * Computes the absolute value of the determinant for the full matrix. * @return {@link Math#abs(double) abs}(determinant) */ public double absDet() { double absDet = 1.0; for(double d : s) absDet *= d; return absDet; } /** * Solves the linear system of equations for A x = b by using the equation
* x = A-1 b = V S-1 UT b *
* When A is not full rank, this results in a more numerically stable approximation that minimizes the least squares error. * * @param b the vector to solve for * @return the vector that gives the least squares solution to A x = b */ public Vec solve(Vec b) { Vec x = U.transposeMultiply(1.0, b); x.mutablePairwiseMultiply(DenseVector.toDenseVec(getInverseSingularValues())); return V.multiply(x); } /** * Solves the linear system of equations for A x = B by using the equation
* x = A-1 B = V S-1 UT B *
* When A is not full rank, this results in a more numerically stable approximation that minimizes the least squares error. * * @param B the matrix to solve for * @return the matrix that gives the least squares solution to A x = B */ public Matrix solve(Matrix B) { Matrix x = U.transposeMultiply(B); Matrix.diagMult(DenseVector.toDenseVec(getInverseSingularValues()), x); return V.multiply(x); } /** * Solves the linear system of equations for A x = B by using the equation
* x = A-1 B = V S-1 UT B *
* When A is not full rank, this results in a more numerically stable approximation that minimizes the least squares error. * * @param b the matrix to solve for * @param threadpool * @return the matrix that gives the least squares solution to A x = B */ public Matrix solve(Matrix b, ExecutorService threadpool) { Matrix x = U.transposeMultiply(b, threadpool); Matrix.diagMult(DenseVector.toDenseVec(getInverseSingularValues()), x); return V.multiply(x, threadpool); } @Override public SingularValueDecomposition clone() { return new SingularValueDecomposition(U.clone(), V.clone(), Arrays.copyOf(s, s.length)); } }

Ads help maintain this website.