Optimal Rank-K Reconstruction from Principal Directions

Why a Principal Subspace Gives a Best Reconstruction

Principal directions describe directions of greatest variance, but their value is not limited to describing variation one direction at a time. Together, the leading directions provide a low-dimensional subspace for approximating a random vector. The relevant question is precise: among all subspaces of a fixed dimension $K$, which one gives the smallest expected squared distance between the vector and its projection?

The answer is the span of the $K$ eigenvectors associated with the largest covariance eigenvalues. The proof connects squared reconstruction error to the covariance trace retained by a projection. It also clarifies the objective: minimizing expected squared distance is not the same as minimizing expected distance.

Setup and Definitions

Let $X$ be a random vector in $\mathbb{R}^p$ with finite second moments, mean $\mu=E[X]$, and covariance matrix $\Sigma=E[(X-\mu)(X-\mu)^\mathsf{T}]$. Because $\Sigma$ is symmetric and positive semidefinite, it has an orthonormal eigenbasis. Write its eigenvalues in decreasing order as $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_p\geq 0$, with corresponding orthonormal eigenvectors $v_1,\ldots,v_p$.

Definition: A rank-$K$ orthogonal projection is a matrix $P$ satisfying $P^\mathsf{T}=P$, $P^2=P$, and $\operatorname{rank}(P)=K$. It projects onto a $K$-dimensional linear subspace. The associated mean-centered reconstruction of $X$ is $\widehat{X}_P=\mu+P(X-\mu)$. Its expected squared reconstruction error is $R(P)=E[\|X-\widehat{X}_P\|^2]$.

The residual is $X-\widehat{X}_P=(I-P)(X-\mu)$. The candidate leading-eigenspace projection is $P_K=\sum_{j=1}^K v_jv_j^\mathsf{T}$, the orthogonal projection onto the span of $v_1,\ldots,v_K$. When $K=0$, the projection is zero; when $K=p$, it is the identity.

Squared Error as Unretained Covariance

The first result translates the reconstruction objective into a matrix quantity. The trace of a matrix is the sum of its diagonal entries; for a covariance matrix it is the total variance across coordinates.

Proposition: For every rank-$K$ orthogonal projection $P$, $$ R(P)=\operatorname{tr}((I-P)\Sigma) =\operatorname{tr}(\Sigma)-\operatorname{tr}(P\Sigma). $$ Thus minimizing expected squared reconstruction error is equivalent to maximizing the covariance trace retained by the projection.

Proof. Put $Y=X-\mu$, so $E[YY^\mathsf{T}]=\Sigma$. Since $P$ is symmetric and idempotent, $I-P$ is also symmetric and idempotent. Therefore $$ \|X-\widehat{X}_P\|^2 =\|(I-P)Y\|^2 =Y^\mathsf{T}(I-P)Y. $$ For any fixed matrix $A$, expanding the quadratic form by entries gives $E[Y^\mathsf{T}AY]=\sum_{r,s}A_{rs}E[Y_rY_s]=\operatorname{tr}(A\Sigma)$. The finite second moments ensure these expectations exist. Taking $A=I-P$ gives $R(P)=\operatorname{tr}((I-P)\Sigma)$. Linearity of trace yields the second equality. $\square$

The proposition makes the optimization target explicit. The total covariance trace does not depend on $P$, so the best projection is the one with the largest $\operatorname{tr}(P\Sigma)$. In an eigenbasis, that retained trace assigns a weight between zero and one to each eigenvalue.

Optimality of the Leading Covariance Directions

Theorem: Suppose $X\in\mathbb{R}^p$ has finite second moments and covariance eigenvalues ordered as above. For any integer $K$ with $0\leq K\leq p$, the projection $P_K$ onto the span of the first $K$ covariance eigenvectors minimizes $R(P)$ over all rank-$K$ orthogonal projections. Its expected squared error is $$ R(P_K)=\sum_{j=K+1}^{p}\lambda_j. $$

Proof. Fix any rank-$K$ orthogonal projection $P$, and define $a_j=v_j^\mathsf{T}Pv_j$. Since $P$ is an orthogonal projection, $a_j=\|Pv_j\|^2$, so $0\leq a_j\leq 1$. Also, using the eigenbasis to calculate the trace, $$ \sum_{j=1}^p a_j=\operatorname{tr}(P)=K, \qquad \operatorname{tr}(P\Sigma)=\sum_{j=1}^p\lambda_j a_j. $$ For $1\leq K<p$, subtract the retained trace of $P$ from the sum of the leading $K$ eigenvalues: $$ \sum_{j=1}^K\lambda_j-\sum_{j=1}^p\lambda_j a_j =\sum_{j=1}^K\lambda_j(1-a_j)-\sum_{j=K+1}^p\lambda_j a_j. $$ For $j\leq K$, $\lambda_j\geq\lambda_K$; for $j>K$, $\lambda_j\leq\lambda_K$. Consequently the right side is at least $$ \lambda_K\left(\sum_{j=1}^K(1-a_j)-\sum_{j=K+1}^p a_j\right)=0, $$ because $\sum_{j=1}^K(1-a_j)=K-\sum_{j=1}^K a_j=\sum_{j=K+1}^p a_j$. Hence $\operatorname{tr}(P\Sigma)\leq\sum_{j=1}^K\lambda_j$. The projection $P_K$ attains this bound: $P_Kv_j=v_j$ for $j\leq K$, and $P_Kv_j=0$ for $j>K$. By the proposition, it therefore minimizes $R(P)$, and its error is $\operatorname{tr}(\Sigma)-\sum_{j=1}^K\lambda_j=\sum_{j=K+1}^p\lambda_j$. For $K=0$ or $K=p$, the only rank-$K$ projection is respectively zero or the identity, and the same conclusion follows directly. $\square$

The proof does not assume that the eigenvalues are distinct. If a tie occurs at the $K$th eigenvalue, there may be more than one subspace attaining the same optimum. What matters for the theorem is the maximal retained trace, not the uniqueness of a particular basis.

Worked Comparisons

Worked Example: Choosing Two Directions in Three Dimensions

Suppose $X=(X_1,X_2,X_3)^\mathsf{T}$ has independent coordinates, each taking the two values $\pm3$, $\pm2$, and $\pm1$, respectively, with equal probabilities. Each coordinate has mean zero, and their variances are $9,4,1$, so $\Sigma=\operatorname{diag}(9,4,1)$. For $K=2$, the leading subspace is the span of $e_1$ and $e_2$, where $e_j$ is the $j$th coordinate vector.

Projection onto that subspace retains $9+4=13$ units of covariance and leaves expected squared error $1$. For comparison, the subspace spanned by $e_1,e_3$ retains $9+1=10$ and leaves error $4$; the subspace spanned by $e_2,e_3$ retains $4+1=5$ and leaves error $9$. In each case the total trace is $9+4+1=14$, and the error is total trace minus retained trace. The leading two directions give the smallest of these errors.

Worked Example: A Rank-One Direction at Any Angle

Let $X$ have mean zero and covariance $\Sigma=\operatorname{diag}(5,2)$. A unit vector $u=(\cos\theta,\sin\theta)^\mathsf{T}$ defines a rank-one projection $P=uu^\mathsf{T}$. Its retained trace is $$ \operatorname{tr}(P\Sigma)=u^\mathsf{T}\Sigma u =5\cos^2\theta+2\sin^2\theta =2+3\cos^2\theta. $$

The total trace is $7$, so the expected squared error is $7-(2+3\cos^2\theta)=5-3\cos^2\theta$. Since $0\leq\cos^2\theta\leq1$, this is at least $2$, attained when $u$ points along $e_1$ (up to sign). For example, at $\theta=\pi/4$, the retained trace is $2+3/2=3.5$, and the error is $7-3.5=3.5$, greater than the optimal error $2$.

Worked Example: Checking the Trace and Error When Eigenvalues Tie

Let $X$ have independent mean-zero coordinates with variances $6,3,3$, so $\Sigma=\operatorname{diag}(6,3,3)$ and the total trace is $6+3+3=12$. For $K=2$, take $w=(\cos\phi)e_2+(\sin\phi)e_3$, a unit vector orthogonal to $e_1$. The projection onto the span of $e_1,w$ retains $$ e_1^\mathsf{T}\Sigma e_1+w^\mathsf{T}\Sigma w =6+3\cos^2\phi+3\sin^2\phi =9. $$

Its expected squared error is therefore $12-9=3$. For comparison, projection onto the span of $e_2,e_3$ retains $3+3=6$, giving error $12-6=6$. The two directions $e_1,w$ attain the optimal retained trace $6+3=9$ for every $\phi$. The three contributions to the total trace sum to $12$; the rank-two reconstruction retains only two directions and thus has error $3$.

What the Objective Does—and Does Not—Say

The theorem is a statement about the expected squared norm of the residual. It follows from a quadratic expression whose expectation is determined by the covariance matrix. Replacing squared error by expected residual length changes the objective; the covariance-trace proof no longer applies.

Worked Example: Expected Length Can Prefer a Different Direction

Let $X_1$ equal $10$ or $-10$, each with probability $0.01$, and equal zero with probability $0.98$. Let $X_2$, independently, equal $1$ or $-1$, each with probability $0.5$. Both means are zero. Their variances are $E[X_1^2]=100(0.02)=2$ and $E[X_2^2]=1$, so the covariance matrix is $\operatorname{diag}(2,1)$. The leading direction is $e_1$.

Projecting onto $e_1$ leaves residual $(0,X_2)$. Its expected length is $E[|X_2|]=1$, while its expected squared length is $E[X_2^2]=1$. Projecting onto $e_2$ leaves residual $(X_1,0)$. Its expected length is $E[|X_1|]=10(0.02)=0.2$, but its expected squared length is $E[X_1^2]=2$. Thus $e_1$ is better for expected squared error, as the theorem says, whereas $e_2$ gives the smaller expected residual length.

A common mistake is to say that the leading principal subspace minimizes “the expected residual” without specifying the loss. The corrected claim is that it minimizes expected squared residual norm among rank-$K$ orthogonal projections of the mean-centered vector. Another useful check is to keep the two trace quantities distinct: $\operatorname{tr}(\Sigma)$ is total variance, while $\operatorname{tr}(P\Sigma)$ is the variance retained by the chosen projection. Their difference is the expected squared reconstruction error.

Key takeaway: For any mean-centered random vector with finite second moments, the leading $K$ covariance eigenvectors maximize retained covariance trace and minimize expected squared reconstruction error. The minimum is the sum of the covariance eigenvalues not retained.

Check Your Understanding

Use the definitions and trace argument above to answer these questions.

For covariance eigenvalues $8,5,2,1$, what is the minimum expected squared error for a rank-two projection?
Why does the identity $R(P)=\operatorname{tr}(\Sigma)-\operatorname{tr}(P\Sigma)$ make maximizing retained trace equivalent to minimizing reconstruction error?
For a rank-one projection onto a unit vector $u$, what is the retained trace in terms of $u$ and $\Sigma$?
In the tied-eigenvalue example, why does the projection onto the span of $e_1,w$ retain $9$, not $12$?
Why does optimality for expected squared residual length not establish optimality for expected residual length?