maspack.matrix

Class SVDecomposition

java.lang.Object

maspack.matrix.SVDecomposition

public class SVDecomposition
extends java.lang.Object

Constructs the singular value decomposition (SVD) of a matrix. This takes the form
M = U S V'
where M is the original matrix, U and V are orthogonal matrices, V' indicates the transpose of V, and S is a diagonal matrix. Once an SVD has been constructed, it can be used to perform various computations related to M, such as solving equations, computing the determinant, or estimating the condition number.

Providing a separate class for the SVD allows an application to perform such decompositions repeatedly without having to reallocate temporary storage space.

Note: by default, this performs a "thin" SVD, where U and V are not necessarily square matrices if the input is not square. To enable a full SVD, such as when necessary for computing null-spaces of non-square matrices, then factor the matrix using the flag FULL_UV.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_ITERATION_LIMIT The default iteration limit for computing the SVD.
static int	FULL_UV Specifies to compute the full SVD decomposition, otherwise only a 'thin' decomposition is computed for non-square matrices
static int	OMIT_U Specifies that matrix U should not be computed.
static int	OMIT_UV Specifies that neither matrix U nor matrix V should not be computed.
static int	OMIT_V Specifies that matrix V should not be computed.

Constructor Summary

Constructors

Constructor and Description
SVDecomposition() Creates an uninitialized SVDecomposition.
SVDecomposition(Matrix M) Creates an SVDecomposition and initializes it to the SVD for the matrix M.
SVDecomposition(Matrix M, int flags) Creates an SVDecomposition and initializes it to the SVD for the matrix M.

Method Summary

Modifier and Type	Method and Description
double	condition() Computes the condition number of the original matrix M associated with this SVD.
double	determinant() Computes the determinant of the original matrix M associated with this SVD.
static SVDecomposition	factor(DenseMatrix U, Vector svec, DenseMatrix V, Matrix M) Convenience method that creates an SVDecomposition, factors it for the matrix M, and stores the resulting U, S and V values into the corresponding arguments.
void	factor(Matrix M) Peforms an SVD on the Matrix M.
void	factor(Matrix M, int flags) Peforms an SVD on the Matrix M.
void	get(DenseMatrix U, Vector svec, DenseMatrix V) Gets the matrices associated with the SVD.
int	getIterationLimit() Gets the iteration limit for SVD computations.
VectorNd	getS() Returns the current singular values associated with this decomposition.
MatrixNd	getU() Returns the current U matrix associated with this decomposition.
MatrixNd	getV() Returns the current V matrix associated with this decomposition.
boolean	inverse(MatrixNd R) Computes the inverse of the original matrix M associated this SVD, and places the result in R.
double	norm() Computes the 2-norm of the original matrix M associated with this SVD.
boolean	pseudoInverse(DenseMatrix R) Computes the pseudo inverse of the original matrix M associated this SVD, and places the result in R.
boolean	pseudoInverse(MatrixNd R) Computes the pseudo inverse of the original matrix M associated this SVD, and places the result in R.
int	rank(double tol) Estimates the rank of the original matrix used to form this decomposition, based on a supplied tolerance tol.
void	setIterationLimit(int lim) Sets the iteration limit for SVD computations.
boolean	solve(DenseMatrix X, DenseMatrix B) Solves the linear equation M X = B where M is the original matrix associated with this SVD, and X and B are matrices.
boolean	solve(DenseMatrix X, DenseMatrix B, double tol) Solves the linear equation M X = B where M is the original matrix associated with this SVD, and X and B are matrices.
boolean	solve(Vector x, Vector b) Solves the linear equation M x = b where M is the original matrix associated with this SVD, and x and b are vectors.
boolean	solve(Vector x, Vector b, double tol) Solves the linear equation M x = b where M is the original matrix associated with this SVD, and x and b are vectors.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

OMIT_U

public static final int OMIT_U

Specifies that matrix U should not be computed.

See Also:

Constant Field Values

OMIT_V

public static final int OMIT_V

Specifies that matrix V should not be computed.

See Also:

Constant Field Values

OMIT_UV

public static final int OMIT_UV

Specifies that neither matrix U nor matrix V should not be computed.

See Also:

Constant Field Values

FULL_UV

public static final int FULL_UV

Specifies to compute the full SVD decomposition, otherwise only a 'thin' decomposition is computed for non-square matrices

See Also:

Constant Field Values

DEFAULT_ITERATION_LIMIT

public static final int DEFAULT_ITERATION_LIMIT

The default iteration limit for computing the SVD.

See Also:

Constant Field Values

Constructor Detail

SVDecomposition

public SVDecomposition(Matrix M)

Creates an SVDecomposition and initializes it to the SVD for the matrix M.

Parameters:

M - matrix to perform the SVD on

SVDecomposition

public SVDecomposition(Matrix M,
                       int flags)

Creates an SVDecomposition and initializes it to the SVD for the matrix M. Computation of U and/or V may be omitted by specifying the flags OMIT_U and/or OMIT_V.

Parameters:

M - matrix to perform the SVD on

flags - flags controlling the factorization

SVDecomposition

public SVDecomposition()

Creates an uninitialized SVDecomposition.

Method Detail

getIterationLimit

public int getIterationLimit()

Gets the iteration limit for SVD computations. The actual number of iterations allowed is this limit value times the minimum dimension of the matrix.

Returns:

iteration limit

See Also:

setIterationLimit(int)

setIterationLimit

public void setIterationLimit(int lim)

Sets the iteration limit for SVD computations. The actual number of iterations allowed is this limit value times the minimum dimension of the matrix.

Parameters:

lim - iteration limit

See Also:

getIterationLimit()

factor

public void factor(Matrix M)

Peforms an SVD on the Matrix M.

Parameters:

M - matrix to perform the SVD on

factor

public void factor(Matrix M,
                   int flags)

Peforms an SVD on the Matrix M. Computation of the matrices U and/or V may be omitted by specifying the flags OMIT_U and/or OMIT_V.

Parameters:

M - matrix to perform the SVD on

flags - controlling the factorization.

get

public void get(DenseMatrix U,
                Vector svec,
                DenseMatrix V)

Gets the matrices associated with the SVD.

Parameters:

U - If not null, returns the left-hand orthogonal matrix

svec - If not null, returns the diagonal elements of S

V - If not null, returns the right-hand orthogonal matrix (note that this is V, and not it's transpose V^T).

Throws:

ImproperStateException - if this SVDecomposition is uninitialized, or if either U or V are requested but were not computed

ImproperSizeException - if U, svec, or V are not of the proper dimension and cannot be resized.

getU

public MatrixNd getU()

Returns the current U matrix associated with this decomposition. If U was not computed, returns null. Subsequent factorizations will cause a different U to be created. The returned matrix should not be modified if any subsequent calls are to be made which depend on U (including solve and inverse methods).

Returns:

current U matrix

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

getV

public MatrixNd getV()

Returns the current V matrix associated with this decomposition. If V was not computed, returns null. Subsequent factorizations will cause a different V to be created. The returned matrix should not be modified if any subsequent calls are to be made which depend on V (including solve and inverse methods).

Returns:

current V matrix

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

getS

public VectorNd getS()

Returns the current singular values associated with this decomposition. Subsequent factorizations will cause a different vector to be created. The returned vector should not be modified if any subsequent calls are to be made which depend on it (including solve and inverse methods).

Returns:

current singular values

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

factor

public static SVDecomposition factor(DenseMatrix U,
                                     Vector svec,
                                     DenseMatrix V,
                                     Matrix M)

Convenience method that creates an SVDecomposition, factors it for the matrix M, and stores the resulting U, S and V values into the corresponding arguments. If the arguments U and/or V are specified as null, then U and/or V will not be computed.

Parameters:

U - If not null, returns the left-hand orthogonal matrix

svec - If not null, returns the diagonal elements of S

V - If not null, returns the right-hand orthogonal matrix (note that this is V, and not it's transpose V^T).

M - matrix to be factored

Returns:

the resulting SVDecomposition

condition

public double condition()

Computes the condition number of the original matrix M associated with this SVD. This is simply the absolute value of the ratio of the maximum and minimum singular values.

Returns:

condition number

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

norm

public double norm()

Computes the 2-norm of the original matrix M associated with this SVD. This is simply the absolute value of the maximum singular value.

Returns:

2-norm

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

determinant

public double determinant()

Computes the determinant of the original matrix M associated with this SVD.

Returns:

determinant

Throws:

ImproperStateException - if this SVDecomposition is uninitialized

solve

public boolean solve(Vector x,
                     Vector b)

Solves the linear equation
M x = b
where M is the original matrix associated with this SVD, and x and b are vectors. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. If m < n, then the system is underdetermined and the minimum norm solution is computed.

This method assumes that M has full rank (i.e., that the minimum singular value is > 0). If it does not, then the method returns false and the solution will likely contain infinite values. To handle situations where M does not have full rank, one should use solve(Vector,Vector,double) instead.

Parameters:

x - unknown vector to solve for

b - constant vector

Returns:

false if M does not have full rank

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if b does not have a size compatible with M, or if x does not have a size compatible with M and cannot be resized.

solve

public boolean solve(Vector x,
                     Vector b,
                     double tol)

Solves the linear equation
M x = b
where M is the original matrix associated with this SVD, and x and b are vectors. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. If m < n, then the system is underdetermined and the minimum norm solution is computed.

To handle situations where M is rank deficient, the calculation ignores singular values whose value is less than or equal to tol*sigmax, where tol is a specified tolerance and is the maximum singular value. Results that would otherwise be obtained by dividing by these values are instead set to zero, resulting in pseudoinverse solutions. Specifying a negative value for tol removes this behavior, so that the resulting solution will be identical to #solve(VectorNd,VectorNd)} and false will be returned if M does not have full rank.

Parameters:

x - unknown vector to solve for

b - constant vector

tol - solution tolerance

Returns:

false if tol is negative and M does not have full rank

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if b does not have a size compatible with M, or if x does not have a size compatible with M and cannot be resized.

solve

public boolean solve(DenseMatrix X,
                     DenseMatrix B)

Solves the linear equation
M X = B
where M is the original matrix associated with this SVD, and X and B are matrices. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. If m < n, then the system is underdetermined and the minimum norm solution (which respect to each column of X) is computed.

This method assumes that M has full rank (i.e., that the minimum singular value is > 0). If it does not, then the method returns false and the solution will likely contain infinite values. To handle situations where M does not have full rank, one should use solve(DenseMatrix,DenseMatrix,double) instead.

Parameters:

X - unknown matrix to solve for

B - constant matrix

Returns:

false if M does not have full rank

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if B has a different number of rows than M, or if the size of X is incompatible with B or M and cannot be resized.

solve

public boolean solve(DenseMatrix X,
                     DenseMatrix B,
                     double tol)

Solves the linear equation
M X = B
where M is the original matrix associated with this SVD, and X and B are matrices. If M has size m X n with m > n, then the system is overdetermined and solution with the minimum least square error is computed. If m < n, then the system is underdetermined and the minimum norm solution (which respect to each column of X) is computed.

To handle situations where M is rank deficient, the calculation ignores singular values whose value is less than or equal to tol*sigmax, where tol is a specified tolerance and is the maximum singular value. Results that would otherwise be obtained by dividing by these values are instead set to zero, resulting in pseudoinverse solutions. Specifying a negative value for tol removes this behavior, so that the resulting solution will be identical to #solve(VectorNd,VectorNd)} and false will be returned if M does not have full rank.

Parameters:

X - unknown matrix to solve for

B - constant matrix

tol - solution tolerance

Returns:

false if tol is negative and M does not have full rank of M is zero

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if B has a different number of rows than M, or if the size of X is incompatible with B or M and cannot be resized.

inverse

public boolean inverse(MatrixNd R)

Computes the inverse of the original matrix M associated this SVD, and places the result in R.

Parameters:

R - matrix in which the inverse is stored

Returns:

false if M is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if M is not square, or if R does not have the same size as M and cannot be resized.

pseudoInverse

public boolean pseudoInverse(MatrixNd R)

Computes the pseudo inverse of the original matrix M associated this SVD, and places the result in R.

Parameters:

R - matrix in which the inverse is stored

Returns:

false if M is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if R does not have the same size as M and cannot be resized.

pseudoInverse

public boolean pseudoInverse(DenseMatrix R)

Computes the pseudo inverse of the original matrix M associated this SVD, and places the result in R.

Parameters:

R - matrix in which the inverse is stored

Returns:

false if M is singular (within working precision)

Throws:

ImproperStateException - if this decomposition is uninitialized, or if U or V were not computed

ImproperSizeException - if R does not have the same size as M and cannot be resized.

rank

public int rank(double tol)

Estimates the rank of the original matrix used to form this decomposition, based on a supplied tolerance tol. The rank is estimated by counting all singular values whose value is greater than smax*tol, where smax is the maximim singular value.

Parameters:

tol - tolerance for estimating the rank

Returns:

estimated rank of the orginal matrix

Throws:

ImproperStateException - if this SVDecomposition is uninitialized