SVDs Of Tall Rectangular Matrices

Why Tall Matrices Need Careful Dimension Tracking

Let \(\mathbf{A}\) be an \(m\times n\) real matrix with \(m>n\). It maps vectors in \(\mathbb{R}^n\) to vectors in the larger space \(\mathbb{R}^m\). If \(\mathbf{A}\) has full column rank, its \(n\) columns are linearly independent. An SVD organizes this map using orthonormal vectors in both spaces, but the two sets of vectors have different dimensions: right singular vectors lie in \(\mathbb{R}^n\), while left singular vectors lie in \(\mathbb{R}^m\).

The key computational starting point is the Gram matrix \(\mathbf{A}^{\top}\mathbf{A}\). Its size is \(n\times n\), so its eigenvectors give the right singular vectors. The corresponding left singular vectors are then constructed from their images under \(\mathbf{A}\). For a full-column-rank tall matrix, this gives \(n\) left singular vectors; a full SVD also requires \(m-n\) additional orthonormal vectors in \(\mathbb{R}^m\).

The Gram Matrix and Positive Singular Values

For a tall \(\mathbf{A}\in\mathbb{R}^{m\times n}\), the product \(\mathbf{A}^{\top}\mathbf{A}\) has size \(n\times n\). It is symmetric. Its eigenvalues determine the singular values: if the eigenvalues are \(\lambda_1\ge\cdots\ge\lambda_n\), the corresponding singular values are \(\sigma_i=\sqrt{\lambda_i}\). The real Spectral Theorem, established in the earlier material, guarantees an orthonormal eigenbasis for a real symmetric matrix.

Proof. To show positive definiteness, take any \(\mathbf{x}\in\mathbb{R}^n\) with \(\mathbf{x}\ne\mathbf{0}\). Then \(\mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}=(\mathbf{A}\mathbf{x})^{\top}(\mathbf{A}\mathbf{x})=\|\mathbf{A}\mathbf{x}\|^2\). Full column rank means \(\mathbf{A}\mathbf{x}\ne\mathbf{0}\), so \(\|\mathbf{A}\mathbf{x}\|^2>0\). Thus \(\mathbf{A}^{\top}\mathbf{A}\) is positive definite. Now let \(\mathbf{v}\ne\mathbf{0}\) be an eigenvector with eigenvalue \(\lambda\). The same computation gives \(\lambda\|\mathbf{v}\|^2=\mathbf{v}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{v}>0\). Since \(\|\mathbf{v}\|^2>0\), it follows that \(\lambda>0\). The Spectral Theorem supplies an eigenbasis, so this applies to every eigenvalue. \(\square\)

Consequently, for a full-column-rank tall matrix there are exactly \(n\) singular values, all positive. The Gram matrix has \(n\) eigenvectors in \(\mathbb{R}^n\); applying \(\mathbf{A}\) to them produces \(n\) vectors in \(\mathbb{R}^m\). Dividing each image by its singular value makes those vectors unit vectors.

Constructing the Left Vectors and the Factorizations

Proof. The eigenvectors satisfy \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_i=\lambda_i\mathbf{v}_i\) and \(\mathbf{v}_i^{\top}\mathbf{v}_j=1\) when \(i=j\), \(0\) otherwise. Since each \(\sigma_i>0\), every \(\mathbf{u}_i\) is defined. For \(1\le i,j\le n\),

Thus the \(\mathbf{u}_i\) are orthonormal. Let \(\mathbf{V}\) have columns \(\mathbf{v}_i\), let \(\mathbf{U}_{\mathrm{thin}}\) have columns \(\mathbf{u}_i\), and let \(\boldsymbol{\Sigma}_{\mathrm{thin}}\) be diagonal with entries \(\sigma_1,\dots,\sigma_n\). Since \(\mathbf{V}\) is an orthogonal \(n\times n\) matrix, \(\mathbf{V}\mathbf{V}^{\top}=\mathbf{I}_n\). Also \(\mathbf{A}\mathbf{v}_i=\sigma_i\mathbf{u}_i\) for each \(i\). Hence \(\mathbf{A}\mathbf{V}=\mathbf{U}_{\mathrm{thin}}\boldsymbol{\Sigma}_{\mathrm{thin}}\), and multiplying on the right by \(\mathbf{V}^{\top}\) proves the thin factorization.

For the full factorization, extend the orthonormal list \(\mathbf{u}_1,\dots,\mathbf{u}_n\) to an orthonormal basis of \(\mathbb{R}^m\). Such an extension can be constructed by repeatedly choosing a standard basis vector outside the current span, subtracting its projections onto the current orthonormal list, and normalizing the nonzero result. This process terminates with \(m\) vectors because the standard basis spans \(\mathbb{R}^m\). Put the added vectors after the \(\mathbf{u}_i\) to form \(\mathbf{U}\), and append \(m-n\) zero rows to \(\boldsymbol{\Sigma}_{\mathrm{thin}}\) to form the \(m\times n\) rectangular diagonal matrix \(\boldsymbol{\Sigma}\). The appended rows contribute zero to the product, so \(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}=\mathbf{A}\). \(\square\)

The thin factorization keeps only the \(n\) left singular vectors needed to represent the columns of \(\mathbf{A}\). The full factorization has a square \(m\times m\) left factor; the extra \(m-n\) columns complete an orthonormal basis, while the corresponding rows of \(\boldsymbol{\Sigma}\) are zero. The right factor remains \(n\times n\) in both forms.

Adding More Left Singular Vectors

Common Pitfall: Using Right Vectors as Left Vectors

The right singular vectors and left singular vectors belong to different spaces. In the three-by-two example, \(\mathbf{v}_1=(1,1)^{\top}/\sqrt{2}\) is a vector in \(\mathbb{R}^2\). A mistaken calculation might declare \(\mathbf{u}_1=\mathbf{v}_1\), then claim \(\mathbf{A}\mathbf{v}_1=\sqrt{3}\mathbf{u}_1\). This is not even a valid vector equality: the left side lies in \(\mathbb{R}^3\), while the proposed right side lies in \(\mathbb{R}^2\). The correction is to compute \(\mathbf{u}_1=\mathbf{A}\mathbf{v}_1/\sigma_1=(1,2,1)^{\top}/\sqrt{6}\), which lies in \(\mathbb{R}^3\) and satisfies \(\mathbf{A}\mathbf{v}_1=\sqrt{3}\mathbf{u}_1\).

A second dimension check catches many errors before any arithmetic: for \(m>n\), the thin factors have sizes \(m\times n\), \(n\times n\), \(n\times n\). The full factors have sizes \(m\times m\), \(m\times n\), \(n\times n\). In particular, the full rectangular diagonal factor has \(m\) rows, not \(n\); its final \(m-n\) rows are zero.