A Worked Rank-K Reconstruction of a Data Matrix

From a Data Matrix to a Rank-\(K\) Reconstruction

A data matrix records several variables on several observations. Principal component analysis can express its variation along orthogonal directions, but a reconstruction makes that expression concrete: it replaces each observation by its representation using only the first \(K\) directions. The resulting matrix is lower rank, and the discrepancy between it and the original data has a precise size.

Here the data matrix \(X\) has \(n\) observations as rows and \(p\) variables as columns. Assume it is centered by columns, so each variable has sample mean zero. We use the singular-value decomposition (SVD) to compute a reconstruction and measure its error. The examples make every matrix product and error calculation explicit.

Definition: Let \(X\) be an \(n\times p\) real matrix, and let \(r=\operatorname{rank}(X)\). A thin SVD is \(X=U_r\Sigma_rV_r^T\), where the columns of \(U_r\) and \(V_r\) are orthonormal and \(\Sigma_r=\operatorname{diag}(\sigma_1,\ldots,\sigma_r)\), with \(\sigma_1\ge\cdots\ge\sigma_r>0\). For an integer \(K\ge 0\), the rank-\(K\) truncated SVD reconstruction is \(X_K=U_K\Sigma_KV_K^T\), using the first \(\min(K,r)\) terms; for \(K=0\), \(X_0=0\).

Equivalently, if the SVD is written with \(q=\min(n,p)\) singular values, including any zeros, then \(X_K=\sum_{j=1}^{K}\sigma_j u_jv_j^T\) when \(K\le q\). The \(j\)th score vector is \(Xv_j=\sigma_j u_j\). Thus the reconstruction retains the first \(K\) score directions and maps those scores back into the original variable coordinates.

Definition: The squared Frobenius norm of a matrix \(A=(a_{ij})\) is \(\|A\|_F^2=\sum_{i,j}a_{ij}^2\). The squared Frobenius reconstruction error of \(X_K\) is \(\|X-X_K\|_F^2\).

Worked Examples

Worked Example: A Rank-One Reconstruction from a Nonorthogonal Pair of Variables

Consider the centered \(3\times2\) matrix

X=\begin{pmatrix} 1&1\\ -1&0\\ 0&-1 \end{pmatrix}.

Each column sums to zero. To find its singular values and right singular vectors, calculate

X^TX=\begin{pmatrix}2&1\\1&2\end{pmatrix}.

The eigenvalues of this matrix are \(3\) and \(1\), with unit eigenvectors \(v_1=(1,1)^T/\sqrt{2}\) and \(v_2=(1,-1)^T/\sqrt{2}\). Therefore the singular values of \(X\) are \(\sigma_1=\sqrt{3}\) and \(\sigma_2=1\). The corresponding left singular vectors are \(u_j=Xv_j/\sigma_j\):

u_1=\frac{1}{\sqrt{6}}\begin{pmatrix}2\\-1\\-1\end{pmatrix}, \qquad u_2=\frac{1}{\sqrt{2}}\begin{pmatrix}0\\-1\\1\end{pmatrix}.

For \(K=1\), retain only the first term. Since \(\sqrt{3}u_1v_1^T\) has rows \((1,1)\), \((-1/2,-1/2)\), and \((-1/2,-1/2)\), the reconstruction and residual are

X_1=\begin{pmatrix} 1&1\\ -\tfrac12&-\tfrac12\\ -\tfrac12&-\tfrac12 \end{pmatrix}, \qquad X-X_1=\begin{pmatrix} 0&0\\ -\tfrac12&\tfrac12\\ \tfrac12&-\tfrac12 \end{pmatrix}.

Adding the four nonzero squared residual entries gives \(\|X-X_1\|_F^2=4(1/2)^2=1\). The discarded singular value gives the same answer: \(\sigma_2^2=1\).

Worked Example: Keeping Two Components of a Three-Variable Matrix

Let the columns of this centered \(4\times3\) matrix be \(4u_1\), \(2u_2\), and \(u_3\), where

u_1=\frac12\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}, \quad u_2=\frac12\begin{pmatrix}1\\1\\-1\\-1\end{pmatrix}, \quad u_3=\frac12\begin{pmatrix}1\\-1\\-1\\1\end{pmatrix}.

These vectors are orthonormal and each sums to zero. The data matrix is

X=\begin{pmatrix} 2&1&\tfrac12\\ -2&1&-\tfrac12\\ 2&-1&-\tfrac12\\ -2&-1&\tfrac12 \end{pmatrix}.

Because the columns are mutually orthogonal and have lengths \(4\), \(2\), and \(1\), respectively, an SVD uses these three unit vectors as its left singular vectors, the \(3\times3\) identity as \(V\), and singular values \(4,2,1\). Retaining \(K=2\) components drops the third column direction:

X_2=\begin{pmatrix} 2&1&0\\ -2&1&0\\ 2&-1&0\\ -2&-1&0 \end{pmatrix}.

The residual has only its third column nonzero, with entries \(1/2,-1/2,-1/2,1/2\). Hence \(\|X-X_2\|_F^2=4(1/2)^2=1\). The singular-value calculation verifies it too: the only discarded singular value is \(1\), whose square is \(1\).

Worked Example: Checking a Rank-One Error in Two Ways

Take two orthonormal centered vectors in four dimensions,

u_1=\frac12\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}, \qquad u_2=\frac12\begin{pmatrix}1\\1\\-1\\-1\end{pmatrix},

and form \(X\) with columns \(3u_1\) and \(2u_2\). Explicitly,

X=\begin{pmatrix} \tfrac32&1\\ -\tfrac32&1\\ \tfrac32&-1\\ -\tfrac32&-1 \end{pmatrix}.

The columns are orthogonal, with lengths \(3\) and \(2\), so the right singular vectors are the two coordinate vectors, and the singular values are \(3\) and \(2\). Keeping \(K=1\) retains the first column and replaces the second by zero:

X_1=\begin{pmatrix} \tfrac32&0\\ -\tfrac32&0\\ \tfrac32&0\\ -\tfrac32&0 \end{pmatrix}.

The four residual entries are \(1,-1,-1,1\) in the second column, so the entrywise error is \(1^2+(-1)^2+(-1)^2+1^2=4\). The discarded singular-value calculation gives \(2^2=4\). Both methods agree.

Why the Discarded Singular Values Give the Error

Theorem: For the truncated SVD \(X_K=\sum_{j=1}^{K}\sigma_j u_jv_j^T\), with zero singular values included if necessary, \(\|X-X_K\|_F^2=\sum_{j>K}\sigma_j^2\).

To prove the identity, write \(X-X_K=\sum_{j>K}\sigma_j u_jv_j^T\). The matrices \(u_jv_j^T\) are orthonormal under the Frobenius inner product: for any indices \(i,j\), \(\langle u_iv_i^T,u_jv_j^T\rangle_F=(u_i^Tu_j)(v_i^Tv_j)\), which is \(1\) when \(i=j\) and \(0\) otherwise. Squaring the norm of the sum therefore leaves only the squared coefficients:

\|X-X_K\|_F^2 = \left\langle\sum_{j>K}\sigma_j u_jv_j^T,\, \sum_{j>K}\sigma_j u_jv_j^T\right\rangle_F = \sum_{j>K}\sigma_j^2.

This proves the formula. It explains why the direct residual calculations in the examples match the singular-value calculations. In practice, the tail sum is a quick check; forming the residual is also useful for confirming the reconstruction’s entries. \(\square\)

Why This Is the Best Rank-\(K\) Approximation

A rank-\(K\) reconstruction is useful because it compresses the matrix while controlling squared error. The truncated SVD does more than provide one such approximation: it minimizes this error among all matrices of rank at most \(K\). The following argument proves this claim for the Frobenius norm.

Theorem (Eckart–Young–Mirsky, Frobenius norm): Let \(X\) have singular values \(\sigma_1\ge\cdots\ge\sigma_q\ge0\), where \(q=\min(n,p)\), and let \(0\le K\le q\). Among all \(n\times p\) matrices \(B\) with \(\operatorname{rank}(B)\le K\), the minimum of \(\|X-B\|_F^2\) is \(\sum_{j>K}\sigma_j^2\), attained by \(X_K\).

The preceding identity shows that \(X_K\) attains this value. To prove no other admissible \(B\) can do better, let \(P\) be the orthogonal projection onto the column space of \(B\). Its rank is at most \(K\), and \((I-P)B=0\). Orthogonal projection cannot increase a vector’s norm, so applying it to every column gives

\|X-B\|_F^2 \ge \|(I-P)(X-B)\|_F^2 =\|(I-P)X\|_F^2 =\|X\|_F^2-\|PX\|_F^2.

Write a full SVD using left singular vectors \(u_1,\ldots,u_q\). Then \(\|PX\|_F^2=\sum_{j=1}^q\sigma_j^2\|Pu_j\|^2\). Set \(a_j=\|Pu_j\|^2\). Since \(P\) is an orthogonal projection, \(0\le a_j\le1\), and \(\sum_{j=1}^q a_j\le\operatorname{rank}(P)\le K\). The first inequality follows by extending \(u_1,\ldots,u_q\) to an orthonormal basis: the sum of \(\|Pu\|^2\) over a complete basis is \(\operatorname{trace}(P)=\operatorname{rank}(P)\), and each omitted term is nonnegative.

Because the weights \(\sigma_j^2\) decrease, these constraints imply \(\sum_{j=1}^q\sigma_j^2a_j\le\sum_{j=1}^K\sigma_j^2\). For \(0<K<q\), one direct verification is

\begin{aligned} \sum_{j=1}^q\sigma_j^2a_j &\le \sum_{j=1}^K\sigma_j^2a_j+ \sigma_K^2\sum_{j>K}a_j\\ &\le \sum_{j=1}^K\left[\sigma_j^2a_j+ \sigma_K^2(1-a_j)\right] \le \sum_{j=1}^K\sigma_j^2. \end{aligned}

The first inequality uses \(\sigma_j^2\le\sigma_K^2\) for \(j>K\); the second uses \(\sum_j a_j\le K\); the third uses \(\sigma_K^2\le\sigma_j^2\) for \(j\le K\). The boundary cases \(K=0\) and \(K=q\) follow directly from the constraints. Thus \(\|PX\|_F^2\le\sum_{j=1}^K\sigma_j^2\), and the earlier display yields \(\|X-B\|_F^2\ge\|X\|_F^2-\sum_{j=1}^K\sigma_j^2=\sum_{j>K}\sigma_j^2\). This proves the claimed minimum, achieved by \(X_K\). \(\square\)

Common Pitfall: Confusing the Error with a Covariance Eigenvalue

A common mistake is to report the discarded eigenvalues of the sample covariance matrix as the squared Frobenius error of the data matrix. For centered \(X\), the sample covariance matrix is \(S=X^TX/(n-1)\), so its eigenvalues are \(\sigma_j^2/(n-1)\), not \(\sigma_j^2\). The squared reconstruction error for \(X\) is \(\sum_{j>K}\sigma_j^2\). If one instead reports the discarded covariance eigenvalues, their sum is the corresponding error divided by \(n-1\).

For example, in the first worked example, \(n=3\) and the discarded singular value is \(1\). The squared matrix reconstruction error is \(1\), whereas the discarded sample-covariance eigenvalue is \(1/(3-1)=1/2\). These quantities answer related but different questions: one is total squared residual across the data entries, and the other is residual variance per sample divisor.

Key takeaway: Compute the truncated reconstruction as \(U_K\Sigma_KV_K^T\), or equivalently as \(\sum_{j=1}^K\sigma_j u_jv_j^T\). Its squared Frobenius error is exactly the sum of the squared singular values left out, and no other rank-\(K\) matrix has smaller squared Frobenius error.

Check Your Understanding

Use the definitions and results above to answer these questions.

For a centered data matrix with singular values \(5,3,1\), what is the squared Frobenius error after retaining \(K=2\) components?
Why does \(X_K\) have rank at most \(K\), even if the original matrix has higher rank?
For the \(3\times2\) worked example, what would the squared reconstruction error be if both components were retained?
Explain why a covariance eigenvalue is not generally the same number as a squared singular value of the data matrix.
In the optimality proof, why is \((I-P)B=0\) when \(P\) projects onto the column space of \(B\)?