Computing An SVD From The Gram Matrix

From the Gram Matrix to an SVD

For a real matrix \(\mathbf{A}\), the matrix \(\mathbf{A}^{\top}\mathbf{A}\) packages information about how \(\mathbf{A}\) acts on vectors in its domain. Its orthonormal eigenvectors provide the right singular vectors of \(\mathbf{A}\), and the square roots of its eigenvalues give the singular values. The remaining task is to turn the images of those right singular vectors into left singular vectors and assemble the factors in the correct order.

Throughout, let \(\mathbf{A}\in\mathbb{R}^{m\times n}\). An SVD, or singular value decomposition, is a factorization \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\), where \(\mathbf{U}\) and \(\mathbf{V}\) are orthogonal matrices and \(\boldsymbol{\Sigma}\) is an \(m\times n\) diagonal-shaped matrix. Orthogonal means that the columns form an orthonormal basis, equivalently \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{I}_m\) and \(\mathbf{V}^{\top}\mathbf{V}=\mathbf{I}_n\). The singular values are the nonnegative diagonal entries of \(\boldsymbol{\Sigma}\), written in decreasing order.

The Gram matrix \(\mathbf{A}^{\top}\mathbf{A}\) is \(n\times n\), symmetric, and positive semidefinite: for every \(\mathbf{x}\in\mathbb{R}^n\), \(\mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=(\mathbf{A}\mathbf{x})^{\top}(\mathbf{A}\mathbf{x})\ge 0\). By the real Spectral Theorem, it has an orthonormal eigenbasis. Also, if \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}=\lambda\mathbf{v}\) with \(\mathbf{v}\ne\mathbf{0}\), then \(\lambda\|\mathbf{v}\|^2=\|\mathbf{A}\mathbf{v}\|^2\ge0\), so every eigenvalue is nonnegative.

Why the Construction Produces Orthonormal Vectors

Before carrying out the procedure, it is useful to check why dividing the images by their singular values works. Take an orthonormal list of eigenvectors \(\mathbf{v}_1,\dots,\mathbf{v}_r\) of \(\mathbf{A}^{\top}\mathbf{A}\) with positive eigenvalues \(\lambda_i=\sigma_i^2\). Define \(\mathbf{u}_i=\mathbf{A}\mathbf{v}_i/\sigma_i\).

Proof. The equation \(\mathbf{A}\mathbf{v}_i=\sigma_i\mathbf{u}_i\) follows from the definition of \(\mathbf{u}_i\), since \(\sigma_i>0\). For any \(i,j\), use the eigenvector equation and the orthonormality of the \(\mathbf{v}_i\):

If \(i\ne j\), then \(\mathbf{v}_i^{\top}\mathbf{v}_j=0\), so \(\mathbf{u}_i^{\top}\mathbf{u}_j=0\). If \(i=j\), then \(\mathbf{v}_i^{\top}\mathbf{v}_i=1\) and \(\lambda_i=\sigma_i^2\), so \(\mathbf{u}_i^{\top}\mathbf{u}_i=1\). These are exactly the required orthogonality and unit-length conditions. \(\square\)

The division in this definition requires a positive singular value. If \(\lambda=0\), then \(\|\mathbf{A}\mathbf{v}\|^2=0\), which gives \(\mathbf{A}\mathbf{v}=\mathbf{0}\); dividing that image by \(\sqrt{\lambda}=0\) is not allowed. Instead, the left singular vectors not yet constructed are chosen to complete the existing orthonormal list to an orthonormal basis of \(\mathbb{R}^m\). Orthonormal completion in a finite-dimensional real inner-product space can be performed by extending a list to a basis and applying Gram–Schmidt.

A Step-by-Step Procedure

Here is the precise reason this procedure gives the original matrix. Let \(r\) be the number of positive Gram eigenvalues, so \(\sigma_1,\dots,\sigma_r>0\) and the remaining eigenvalues are zero. For \(j>r\), the norm identity gives \(\|\mathbf{A}\mathbf{v}_j\|^2=0\), hence \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\). The constructed \(\mathbf{u}_1,\dots,\mathbf{u}_r\) are orthonormal, so \(r\le m\) and they can be completed to \(m\) orthonormal vectors.

Proof. The positive-eigenvalue vectors constructed as \(\mathbf{u}_i\) are orthonormal by the proposition. For every remaining eigenvector, \(\lambda_j=0\), and \(\|\mathbf{A}\mathbf{v}_j\|^2=\lambda_j\|\mathbf{v}_j\|^2=0\), so \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\). The columns of \(\mathbf{V}\) form an orthonormal basis, and therefore \(\mathbf{I}_n=\sum_{j=1}^n\mathbf{v}_j\mathbf{v}_j^{\top}\). It follows that \(\mathbf{A}=\mathbf{A}\mathbf{I}_n=\sum_{j=1}^n(\mathbf{A}\mathbf{v}_j)\mathbf{v}_j^{\top}=\sum_{i=1}^r\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\). In \(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\), each positive diagonal entry contributes exactly \(\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\); every other diagonal entry is zero, so the completed left vectors contribute nothing further. Thus this product equals the displayed sum and hence equals \(\mathbf{A}\). \(\square\)

Worked Calculations

Common Mistakes to Avoid

Using an eigenvalue as the singular value. In the last example, the largest Gram eigenvalue is \(9\), but the corresponding singular value is \(\sqrt{9}=3\), not \(9\). If one incorrectly places \(9\) on the diagonal and uses the same left and right vectors, the first rank-one term becomes \(9\mathbf{v}_1\mathbf{v}_1^{\top}\) instead of \(3\mathbf{v}_1\mathbf{v}_1^{\top}\); it does not reproduce \(\mathbf{A}\).

Dividing by zero. If \(\lambda_i=0\), then \(\mathbf{A}\mathbf{v}_i=\mathbf{0}\), but \(\mathbf{A}\mathbf{v}_i/\sqrt{\lambda_i}\) is undefined. Complete the left orthonormal basis using vectors orthogonal to those already found. Then check the resulting columns directly, as in the second example.

Checking only the factor sizes is not enough. A proposed SVD also requires orthonormal columns in \(\mathbf{U}\) and \(\mathbf{V}\), correct square roots on the diagonal, and a product equal to the original matrix. Multiplying the factors back is a direct way to catch sign, ordering, or scaling errors.