In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix into a rotation, followed by a scaling, 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, and is a common means for implementing low-rank approximation for matrices.
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 decompositions always exist for any complex matrix. If is real, then some and can be found which are real (orthogonal) matrices; a real-valued SVD is often denoted , where is the transpose of .
The diagonal entries of are uniquely determined by , up to reordering, and are known as the singular values of . Conventionally they are arranged in descending order (from largest to smallest), which uniquely determines . The number of non-zero singular values, allowing repetitions, 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 orthonormal bases, and . In general the SVD is not unique, with certain unitary transformations of and producing valid alternative decompositions.
The term SVD sometimes refers to the compact SVD, a similar decomposition , in which is an matrix with only the non-zero singular values (allowing repetitions) on its main diagonal. In this variant, is an semi-unitary matrix whose columns span the columns of , and is an semi-unitary matrix whose columns span the columns of .
The SVD (with sorted singular values) splits into a sum of rank- matrices,
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/reflection, coordinate scaling, rotation/reflection In the special case when is an real square matrix, the matrices and can be chosen to be real orthogonal matrices. can be interpreted to represent a linear transformation of the Euclidean space ; then the matrices and represent rotations or reflections 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 geometric 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.
In the more general case when 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 and Σ, 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 (tilted) 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 row space of in the real case). The last columns of are a basis of the null space of .
Geometric meaning Because and are unitary, the columns of are an orthonormal basis of and the columns of are an orthonormal basis of (with respect to the standard scalar products on these spaces).
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 unit sphere 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-axis lengths of as scaling 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 For example, the following matrix can be decomposed as :
The singular values of are the diagonal entries of : , , , . The corresponding left- and right-singular vectors are the columns of and rows of , respectively. That is,
The matrices and are unitary (and, as real-valued matrices, orthogonal), meaning and , where is the identity matrix.
The matrix has rank , so it has only three non-zero singular values. This particular singular value decomposition is not unique. (See , below.) Any column of and the corresponding row of can be simultaneously multiplied by (or, if is considered to be a complex-valued matrix, by any unit complex number) to obtain a valid SVD. The last two rows of do not contribute to the product because they are multiplied by zero, so are substantially arbitrary, and can be replaced with any pair of unit row vectors which are orthogonal to each other and the other rows. Similarly, the last column of can be multiplied by (or by any unit complex number).
The compact SVD eliminates the rows and columns from which consist entirely of zeros, and also the superfluous corresponding columns of and rows of :
Instead of the product of three matrices, the SVD of can be written as a sum of rank- matrices, each formed as the outer product of one column of times the corresponding row of , scaled by the corresponding singular value :
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 comprise the singular values of . The first columns of and are, respectively, left- and right-singular vectors for the corresponding singular values. Consequently, 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 .
The diagonal entries of need not be distinct. A singular value which appears among them times has a -dimensional subspace of corresponding left-singular vectors. Any orthonormal basis for this subspace can be taken as the corresponding columns of some matrix , and uniquely determines an orthonormal basis for the -dimensional subspace of right-singular vectors which form the corresponding columns of a matrix . When and , the singular value is called non-degenerate, and the corresponding left-singular vector and right-singular vector are unique up to multiplication by a phase factor (a unit complex number), or, in the real case, unique up to sign. When , the singular value is called degenerate.
The left- and right-singular vectors of singular value comprise all unit vectors in the cokernel and kernel, respectively, of . By the rank–nullity theorem, these subspaces cannot have the same dimension if . Even when all singular values are non-zero, if , then the cokernel is non-trivial, in which case is padded with orthogonal unit vectors from the cokernel. Conversely, if , then is padded by orthogonal unit vectors from the kernel. However, if the singular value exists, the extra columns of or already appear as left- or right-singular vectors.[…, if the singular value 0 exists, the extra columns of U or V must not repeat the corresponding left- or right-singular vectors.] [Otherwise, U or V would not have column full rank.]
If all singular values of a square matrix are non-zero and non-degenerate, then its singular value decomposition is unique up to multiplication of any column of and the corresponding column of by an arbitrary phase factor. More generally, the SVD of any matrix is unique up to unitary transformations applied uniformly to the column vectors of both and (and which do not mix columns corresponding to distinct singular values).
Relation to eigenvalue decomposition The singular value decomposition is very general in the sense that it can be applied to any matrix, whereas eigenvalue decomposition can only be applied to square diagonalizable matrices. Nevertheless, the two decompositions are related.
If has SVD , the following two relations hold:
The right-hand sides of these relations describe the eigenvalue decompositions of the left-hand sides. Consequently:
The columns of (referred to as right-singular vectors) are eigenvectors of . The columns of (referred to as left-singular vectors) are eigenvectors of . The non-zero elements of (non-zero singular values) are the square roots of the non-zero eigenvalues of or .