Extreme Optimization >
User's Guide >
Vector and Matrix Library >
Matrix Decompositions >
The Singular Value Decomposition
Extreme Optimization User's Guide
User's Guide
Up: Matrix Decompositions Next: Solving Linear Systems and Related Operations Previous: The Non-Symmetric Eigenvalue Decomposition Contents
The Singular Value Decomposition
The Singular Value Decomposition or SVD of a matrix expresses
the matrix as the product of an orthogonal matrix, a diagonal
matrix, and an orthogonal matrix. The matrix can be of any type,
and of any shape.The SVD decomposition is usually written as
A = USVT,
where U and V are square, orthogonal matrices,
and S is a diagonal matrix with the same shape as
A.
The singular value decomposition is the most stable of all
decompositions. Aside from its own, unique, uses, it is used in
situations where the highest possible accuracy is required. The
numerical rank is determined using the singular value
decomposition, as is the exact condition number, which is the ratio
of the largest to the smallest singular value. On the downside, the
method is slower than all other decompositions.
In the Extreme Optimization Mathematics Library for
.NET, the singular value decomposition is implemented by the
SingularValueDecomposition
class.
The SingularValueDecomposition
class represents the singular value decomposition of a matrix.
It has four constructors. The first variant takes a
Matrix
as its only parameter.
| C# |  Copy Code |
|---|
GeneralMatrix aSVD = new GeneralMatrix(4, 4,
new double[]
{
1.80, 5.25, 1.58, -1.11,
2.88,-2.95, -2.69, -0.66,
2.05,-0.95, -2.90, -0.59,
-0.89,-3.80,-1.04, 0.80
});
SingularValueDecomposition svd = new SingularValueDecomposition(aSVD); |
| Visual Basic | Copy Code |
|---|
Dim aSVD As GeneralMatrix = New GeneralMatrix(4, 4, _
New Double() _
{ _
1.8, 5.25, 1.58, -1.11, _
2.88, -2.95, -2.69, -0.66, _
2.05, -0.95, -2.9, -0.59, _
-0.89, -3.8, -1.04, 0.8 _
})
Dim svd As SingularValueDecomposition = _
New SingularValueDecomposition(aSVD) |
The second constructor takes a GeneralMatrix
as its first parameter. The second parameter is a
Boolean value that specifies whether the contents of
the first parameter should be overwritten by the SVD
decomposition. The default is false.
| C# | Copy Code |
|---|
SingularValueDecomposition svd2 = new SingularValueDecomposition(A, true); |
| Visual Basic | Copy Code |
|---|
Dim svd2 As SingularValueDecomposition = _
New SingularValueDecomposition(A, True) |
The two remaining constructors let you specify which
calculations are to be performed. Because the calculation of the
left and right singular vectors is relatively expensive and not
always needed, it is possible to specify that only the singular
values need to be computed. This is done in one of two ways. The
first is by passing a value of type
SingularValueDecompositionFactors to the constructor
as the second parameter. Alternatively, you can set the
RequestedFactors property to a value of the same type
before the decomposition is computed. The possible values for the
SingularValueDecompositionFactors enumeration are
listed below:
| Value |
Description |
| SingularValues |
The singular values are required. This is always included. |
| LeftSingularVectors |
The left singular vectors are required. |
| RightSingularVectors |
The right singular vectors are required. |
| All |
The singular values as well as the left and right singular
vectors are required. |
Table 1. Possible values for the
SingularValueDecompositionFactors
enumeration.
The
Decompose method performs the actual decomposition.
This method copies the matrix if necessary. It then calls the
appropriate LAPACK routine to perform the actual decomposition.
This method is called by other methods as needed. You will rarely
need to call it explicitly.
Once the decomposition is computed, a number of operations can
be performed in much less time. You can repeatedly solve a system
of simultaneous linear equations with different right-hand sides.
You can also calculate the determinant (only the magnitude) and the
inverse of the base matrix:
| C# | Copy Code |
|---|
GeneralMatrix bSVD = new GeneralMatrix(4, 2, new double[]
{
9.52,24.35,0.77,-6.22,
18.47,2.25,-13.28,-6.21
});
Matrix xSVD = lu.Solve(bSVD);
Console.WriteLine("Ax = b -> x = {0}", xSVD);
Console.WriteLine("Inv A = {0}", svd.GetInverse().ToString("F4"));
Console.WriteLine("Det A = {0}", svd.GetDeterminant()); |
| Visual Basic | Copy Code |
|---|
Dim bSVD As GeneralMatrix = New GeneralMatrix(4, 2, New Double() _
{ _
9.52, 24.35, 0.77, -6.22, _
18.47, 2.25, -13.28, -6.21 _
})
Dim xSVD As Matrix = lu.Solve(bSVD)
Console.WriteLine("Ax = b -> x = {0}", xSVD)
Console.WriteLine("Inv A = {0}", svd.GetInverse().ToString("F4"))
Console.WriteLine("Det A = {0}", svd.GetDeterminant()) |
A number of methods are unique to the singular value
decomposition. The
GetPseudoInverse method returns
a GeneralMatrix
that is the Moore-Penrose pseudo-inverse of the matrix. A
pseudo-inverse is a generalization of the inverse of a matrix to
matrices that are not square or singular. The Moore-Penrose
pseudo-inverse is the most common, and is defined as the unique
matrix A+ that satisfies the following four
conditions:
| AA+A = A |
(AA+)T =AA+ |
| A+AA+ =A+ |
(A+A)T =A+A |
The
SingularValues property returns
a GeneralVector
containing the singular values in decreasing order. The
SingularValueMatrix property returns
a DiagonalMatrix
with the same shape as the decomposed matrix with the singular
values on the diagonal in decreasing order.
The
LeftSingularVectors and
RightSingularVectors properties return
a GeneralMatrix
whose columns are the left and right singular vectors corresponding
to each singular value. When the number of rows of the matrix
equals the number of columns, these matrices correspond to the
matrices U and V of the decomposition. If the
number of rows is greater than the number of columns, then
LeftSingularVectors only returns the first
c columns of U, where c is the
number of columns. If the number of rows is less than the number of
columns, then RightSingularVectors only returns the
first r columns of V, where r is
the number of rows.
| C# | Copy Code |
|---|
Console.WriteLine("S = {0:F4}", svd.SingularValues)
Console.WriteLine("U = {0:F4}", svd.LeftSingularVectors)
Console.WriteLine("V = {0:F4}", svd.RightSingularVectors) |
| Visual Basic | Copy Code |
|---|
Console.WriteLine("S = {0:F4}", svd.SingularValues)
Console.WriteLine("U = {0:F4}", svd.LeftSingularVectors)
Console.WriteLine("V = {0:F4}", svd.RightSingularVectors) |
The managed implementation of the singular value decomposition
is based on the LINPACK routine DSVDC. The native version uses the
LAPACK routine DGESDD.
Up: Matrix Decompositions Next: Solving Linear Systems and Related Operations Previous: The Non-Symmetric Eigenvalue Decomposition Contents
Copyright 2004-2008,
Extreme Optimization. All rights reserved.
Extreme Optimization, Complexity made simple, M#, and M
Sharp are trademarks of ExoAnalytics Inc.
Microsoft, Visual C#, Visual Basic, Visual Studio, Visual
Studio.NET, and the Visual Studio Logo are registered trademarks of Microsoft Corporation