Class SVD


  • public class SVD
    extends java.lang.Object
    Singular Value Decomposition.

    For an m-by-n matrix A with m ≥ n, the singular value decomposition is an m-by-n orthogonal matrix U, an n-by-n diagonal matrix Σ, and an n-by-n orthogonal matrix V so that A = U*Σ*V'.

    For m < n, only the first m columns of V are computed and Σ is m-by-m.

    The singular values, σk = Σkk, are ordered so that σ0 ≥ σ1 ≥ ... ≥ σn-1.

    The singular value decompostion always exists. The matrix condition number and the effective numerical rank can be computed from this decomposition.

    SVD is a very powerful technique for dealing with sets of equations or matrices that are either singular or else numerically very close to singular. In many cases where Gaussian elimination and LU decomposition fail to give satisfactory results, SVD will diagnose precisely what the problem is. SVD is also the method of choice for solving most linear least squares problems.

    Applications which employ the SVD include computing the pseudoinverse, least squares fitting of data, matrix approximation, and determining the rank, range and null space of a matrix. The SVD is also applied extensively to the study of linear inverse problems, and is useful in the analysis of regularization methods such as that of Tikhonov. It is widely used in statistics where it is related to principal component analysis. Yet another usage is latent semantic indexing in natural language text processing.

    Author:
    Haifeng Li
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected boolean full
      Is this a full decomposition?
      protected int m
      The number of rows.
      protected int n
      The number of columns.
      protected double[] s
      Array for internal storage of singular values.
      protected double tol
      Threshold of estimated roundoff.
      protected DenseMatrix U
      Arrays for internal storage of left singular vectors U.
      protected DenseMatrix V
      Arrays for internal storage of right singular vectors V.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Cholesky CholeskyOfAtA()
      Returns the Cholesky decomposition of A'A.
      double condition()
      Returns the L2 norm condition number, which is max(S) / min(S).
      DenseMatrix getS()
      Returns the diagonal matrix of singular values
      double[] getSingularValues()
      Returns the one-dimensional array of singular values, ordered by from largest to smallest.
      DenseMatrix getU()
      Returns the left singular vectors
      DenseMatrix getV()
      Returns the right singular vectors
      double norm()
      Returns the L2 matrix norm.
      int nullity()
      Returns the dimension of null space.
      DenseMatrix nullspace()
      Returns a matrix of which columns give an orthonormal basis for the null space.
      DenseMatrix range()
      Returns a matrix of which columns give an orthonormal basis for the range space.
      int rank()
      Returns the effective numerical matrix rank.
      void solve​(double[] b, double[] x)
      Solve the least squares A*x = b.
      void solve​(DenseMatrix B)
      Solve the least squares A * X = B.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • U

        protected DenseMatrix U
        Arrays for internal storage of left singular vectors U.
      • V

        protected DenseMatrix V
        Arrays for internal storage of right singular vectors V.
      • s

        protected double[] s
        Array for internal storage of singular values.
      • full

        protected boolean full
        Is this a full decomposition?
      • m

        protected int m
        The number of rows.
      • n

        protected int n
        The number of columns.
      • tol

        protected double tol
        Threshold of estimated roundoff.
    • Method Detail

      • getU

        public DenseMatrix getU()
        Returns the left singular vectors
      • getV

        public DenseMatrix getV()
        Returns the right singular vectors
      • getSingularValues

        public double[] getSingularValues()
        Returns the one-dimensional array of singular values, ordered by from largest to smallest.
      • getS

        public DenseMatrix getS()
        Returns the diagonal matrix of singular values
      • norm

        public double norm()
        Returns the L2 matrix norm. The largest singular value.
      • rank

        public int rank()
        Returns the effective numerical matrix rank. The number of nonnegligible singular values.
      • nullity

        public int nullity()
        Returns the dimension of null space. The number of negligible singular values.
      • condition

        public double condition()
        Returns the L2 norm condition number, which is max(S) / min(S). A system of equations is considered to be well-conditioned if a small change in the coefficient matrix or a small change in the right hand side results in a small change in the solution vector. Otherwise, it is called ill-conditioned. Condition number is defined as the product of the norm of A and the norm of A-1. If we use the usual L2 norm on vectors and the associated matrix norm, then the condition number is the ratio of the largest singular value of matrix A to the smallest. Condition number depends on the underlying norm. However, regardless of the norm, it is always greater or equal to 1. If it is close to one, the matrix is well conditioned. If the condition number is large, then the matrix is said to be ill-conditioned. A matrix that is not invertible has the condition number equal to infinity.
      • range

        public DenseMatrix range()
        Returns a matrix of which columns give an orthonormal basis for the range space.
      • nullspace

        public DenseMatrix nullspace()
        Returns a matrix of which columns give an orthonormal basis for the null space.
      • CholeskyOfAtA

        public Cholesky CholeskyOfAtA()
        Returns the Cholesky decomposition of A'A.
      • solve

        public void solve​(double[] b,
                          double[] x)
        Solve the least squares A*x = b.
        Parameters:
        b - right hand side of linear system.
        x - the output solution vector that minimizes the L2 norm of A*x - b.
        Throws:
        java.lang.RuntimeException - if matrix is rank deficient.
      • solve

        public void solve​(DenseMatrix B)
        Solve the least squares A * X = B. B will be overwritten with the solution matrix on output.
        Parameters:
        B - right hand side of linear system. B will be overwritten with the solution matrix on output.
        Throws:
        java.lang.RuntimeException - Matrix is rank deficient.