An
where
where s=min and
Note that if , then and both have the same eigenvalues:
(left-multiply both sides by )
The time-complexity for computing the SVD factorization of an arbitrary
In general, we can define the cost as:
The SVD factorization of a non-square matrix
The following figure depicts the reduced SVD factorization (in red) against the full SVD factorizations (in gray).
In general, we will represent the reduced SVD as:
where is a matrix, is a matrix, is a matrix, and .
We begin with the following non-square matrix,
and we will compute the reduced form of the SVD (where here ):
(1) Compute
(2) Compute the eigenvectors and eigenvalues of
(3) Construct
(4) Construct
(5) Find
We obtain the following singular value decomposition for
Recall that we computed the reduced SVD factorization (i.e.
Suppose is a matrix where (without loss of generality):
We can re-write the above as:
Furthermore, the product of two matrices can be written as a sum of outer products:
For a general rectangular matrix, we have:
where .
If has non-zero singular values, the matrix is full rank, i.e. .
If has non-zero singular values, and , the matrix is rank deficient, i.e. .
In other words, the rank of equals the number of non-zero singular values which is the same as the number of non-zero diagonal elements in .
Rounding errors may lead to small but non-zero singular values in a rank deficient matrix. Singular values that are smaller than a given tolerance are assumed to be numerically equivalent to zero, defining what is sometimes called the effective rank.
The right-singular vectors (columns of ) corresponding to vanishing singular values of span the null space of , i.e. null() = span{, , …, }.
The left-singular vectors (columns of ) corresponding to the non-zero singular values of span the range of , i.e. range() = span{, , …, }.
The rank of is 2.
The vectors and provide an orthonormal basis for the range of .
The vector provides an orthonormal basis for the null space of .
If the matrix is rank deficient, we cannot get its inverse. We define instead the pseudoinverse:
For a general non-square matrix
For example, if we consider a full rank matrix where :
The induced 2-norm of a matrix can be obtained using the SVD of the matrix :
And hence,
In the above equations, all the notations for the norm refer to the Euclidean norm, and we used the fact that and are orthogonal matrices and hence .
We begin with the following non-square matrix :
The matrix of singular values,
Consequently the 2-norm of
Following the same derivation as above, we can show that for a full rank matrix we have:
where is the smallest singular value.
For non-square matrices, we can use the definition of the pseudoinverse (regardless of the rank):
where is the smallest non-zero singular value. Note that for a full rank square matrix, we have . An exception of the definition above is the zero matrix. In this case,
The 2-norm condition number of a matrix
If the matrix is rank deficient, i.e. , then .
The best rank- approximation for a matrix , where , for some matrix norm , is one that minimizes the following problem:
Under the induced
Observe that the norm of the difference between the best approximation and the matrix under the induced
Note that the best rank- approximation to can be stored efficiently by only storing the singular values , the left singular vectors , and the right singular vectors .
The figure below show best rank-