Singular value decomposition


In linear algebra, the singular value decomposition is a factorization of a real or complex matrix into a rotation, followed by a rescaling followed by another rotation. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any matrix. It is related to the polar decomposition.
Specifically, the singular value decomposition of an complex matrix is a factorization of the form where is an complex unitary matrix, is an rectangular diagonal matrix with non-negative real numbers on the diagonal, is an complex unitary matrix, and is the conjugate transpose of. Such decomposition always exists for any complex matrix. If is real, then and can be guaranteed to be real orthogonal matrices; in such contexts, the SVD is often denoted
The diagonal entries of are uniquely determined by and are known as the singular values of. The number of non-zero singular values is equal to the rank of. The columns of and the columns of are called left-singular vectors and right-singular vectors of, respectively. They form two sets of orthonormal bases and and if they are sorted so that the singular values with value zero are all in the highest-numbered columns, the singular value decomposition can be written as
where is the rank of
The SVD is not unique. However, it is always possible to choose the decomposition such that the singular values are in descending order. In this case, is uniquely determined by
The term sometimes refers to the compact SVD, a similar decomposition in which is square diagonal of size where is the rank of and has only the non-zero singular values. In this variant, is an semi-unitary matrix and is an semi-unitary matrix, such that
Mathematical applications of the SVD include computing the pseudoinverse, matrix approximation, and determining the rank, range, and null space of a matrix. The SVD is also extremely useful in many areas of science, engineering, and statistics, such as signal processing, least squares fitting of data, and process control.

Intuitive interpretations

Rotation, coordinate scaling, and reflection

In the special case when is an real square matrix, the matrices and can be chosen to be real matrices too. In that case, "unitary" is the same as "orthogonal". Then, interpreting both unitary matrices as well as the diagonal matrix, summarized here as as a linear transformation of the space the matrices and represent rotations or reflection of the space, while represents the scaling of each coordinate by the factor Thus the SVD decomposition breaks down any linear transformation of into a composition of three geometrical transformations: a rotation or reflection followed by a coordinate-by-coordinate scaling followed by another rotation or reflection
In particular, if has a positive determinant, then and can be chosen to be both rotations with reflections, or both rotations without reflections. If the determinant is negative, exactly one of them will have a reflection. If the determinant is zero, each can be independently chosen to be of either type.
If the matrix is real but not square, namely with it can be interpreted as a linear transformation from to Then and can be chosen to be rotations/reflections of and respectively; and besides scaling the first coordinates, also extends the vector with zeros, i.e. removes trailing coordinates, so as to turn into

Singular values as semiaxes of an ellipse or ellipsoid

As shown in the figure, the singular values can be interpreted as the magnitude of the semiaxes of an ellipse in 2D. This concept can be generalized to -dimensional Euclidean space, with the singular values of any square matrix being viewed as the magnitude of the semiaxis of an -dimensional ellipsoid. Similarly, the singular values of any matrix can be viewed as the magnitude of the semiaxis of an -dimensional ellipsoid in -dimensional space, for example as an ellipse in a 2D plane in a 3D space. Singular values encode magnitude of the semiaxis, while singular vectors encode direction. See [|below] for further details.

The columns of and are orthonormal bases

Since and are unitary, the columns of each of them form a set of orthonormal vectors, which can be regarded as basis vectors. The matrix maps the basis vector to the stretched unit vector By the definition of a unitary matrix, the same is true for their conjugate transposes and except the geometric interpretation of the singular values as stretches is lost. In short, the columns of and are orthonormal bases. When is a positive-semidefinite Hermitian matrix, and are both equal to the unitary matrix used to diagonalize However, when is not positive-semidefinite and Hermitian but still diagonalizable, its eigendecomposition and singular value decomposition are distinct.

Relation to the four fundamental subspaces

  • The first columns of are a basis of the column space of.
  • The last columns of are a basis of the null space of.
  • The first columns of are a basis of the column space of .
  • The last columns of are a basis of the null space of.

    Geometric meaning

Because and are unitary, we know that the columns of yield an orthonormal basis of and the columns of yield an orthonormal basis of .
The linear transformation
has a particularly simple description with respect to these orthonormal bases: we have
where is the -th diagonal entry of and for
The geometric content of the SVD theorem can thus be summarized as follows: for every linear map one can find orthonormal bases of and such that maps the -th basis vector of to a non-negative multiple of the -th basis vector of and sends the leftover basis vectors to zero. With respect to these bases, the map is therefore represented by a diagonal matrix with non-negative real diagonal entries.
To get a more visual flavor of singular values and SVD factorization – at least when working on real vector spaces – consider the sphere of radius one in The linear map maps this sphere onto an ellipsoid in Non-zero singular values are simply the lengths of the semi-axes of this ellipsoid. Especially when and all the singular values are distinct and non-zero, the SVD of the linear map can be easily analyzed as a succession of three consecutive moves: consider the ellipsoid and specifically its axes; then consider the directions in sent by onto these axes. These directions happen to be mutually orthogonal. Apply first an isometry sending these directions to the coordinate axes of On a second move, apply an endomorphism diagonalized along the coordinate axes and stretching or shrinking in each direction, using the semi-axes lengths of as stretching coefficients. The composition then sends the unit-sphere onto an ellipsoid isometric to To define the third and last move, apply an isometry to this ellipsoid to obtain As can be easily checked, the composition coincides with

Example

Consider the matrix
A singular value decomposition of this matrix is given by
The scaling matrix is zero outside of the diagonal and one diagonal element is zero. Furthermore, because the matrices and are unitary, multiplying by their respective conjugate transposes yields identity matrices, as shown below. In this case, because and are real valued, each is an orthogonal matrix.
This particular singular value decomposition is not unique. For instance, we can keep and the same, but change the last two rows of such that
and get an equally valid singular value decomposition. As the matrix has rank 3, it has only 3 nonzero singular values. In taking the product, the final column of and the final two rows of are multiplied by zero, so have no effect on the matrix product, and can be replaced by any unit vectors which are orthogonal to the first three and to each-other.
The compact SVD,, eliminates these superfluous rows, columns, and singular values:

SVD and spectral decomposition

Singular values, singular vectors, and their relation to the SVD

A non-negative real number is a singular value for if and only if there exist unit vectors in and in such that
The vectors and are called left-singular and right-singular vectors for respectively.
In any singular value decomposition
the diagonal entries of are equal to the singular values of The first columns of and are, respectively, left- and right-singular vectors for the corresponding singular values. Consequently, the above theorem implies that:
  • An matrix has at most distinct singular values.
  • It is always possible to find a unitary basis for with a subset of basis vectors spanning the left-singular vectors of each singular value of
  • It is always possible to find a unitary basis for with a subset of basis vectors spanning the right-singular vectors of each singular value of
A singular value for which we can find two left singular vectors that are linearly independent is called degenerate. If and are two left-singular vectors which both correspond to the singular value σ, then any normalized linear combination of the two vectors is also a left-singular vector corresponding to the singular value σ. The similar statement is true for right-singular vectors. The number of independent left and right-singular vectors coincides, and these singular vectors appear in the same columns of and corresponding to diagonal elements of all with the same value
As an exception, the left and right-singular vectors of singular value 0 comprise all unit vectors in the cokernel and kernel, respectively, of which by the rank–nullity theorem cannot be the same dimension if Even if all singular values are nonzero, if then the cokernel is nontrivial, in which case is padded with orthogonal vectors from the cokernel. Conversely, if then is padded by orthogonal vectors from the kernel. However, if the singular value of exists, the extra columns of or already appear as left or right-singular vectors.
Non-degenerate singular values always have unique left- and right-singular vectors, up to multiplication by a unit-phase factor . Consequently, if all singular values of a square matrix are non-degenerate and non-zero, then its singular value decomposition is unique, up to multiplication of a column of by a unit-phase factor and simultaneous multiplication of the corresponding column of by the same unit-phase factor.
In general, the SVD is unique up to arbitrary unitary transformations applied uniformly to the column vectors of both and spanning the subspaces of each singular value, and up to arbitrary unitary transformations on vectors of and spanning the kernel and cokernel, respectively, of