Why Constrain a Principal Component?
A principal component is a linear combination of measured variables chosen to capture variation. In a high-dimensional analysis, however, an ordinary principal component can assign nonzero loadings to nearly every variable. That may make the component difficult to interpret or use. Sparse PCA addresses this issue by requiring a loading vector to have at most a specified number of nonzero entries.
The constraint changes the optimization problem itself: the goal is still to capture as much projected variance as possible, but only among combinations that use a limited number of variables. This is not generally the same as computing an ordinary principal component and deleting its small loadings afterward. Deletion can change the vector’s norm and its variance, and the resulting vector need not be the best one under the sparsity constraint.
Constrained Variance Formulation
Let \(X\) be an \(n\times p\) data matrix whose columns are centered, and let \(S=X^\top X/(n-1)\) be the sample covariance matrix, with \(n>1\). For a unit vector \(v\in\mathbb{R}^p\), the projected observations are the entries of \(Xv\). Their sample variance is \(v^\top S v\). If the covariance matrix is known rather than estimated, the same formulation uses that covariance matrix in place of \(S\).
The unit-norm condition fixes the scale of the loading vector: without it, multiplying \(v\) by a constant would multiply the objective by the square of that constant. The sign is not identified by the objective, since \((-v)^\top S(-v)=v^\top S v\). Thus \(v\) and \(-v\) describe the same variance-maximizing direction.
The Geometry of the Constraint
For each coordinate set \(T\subseteq\{1,\ldots,p\}\), consider the vectors that are zero outside \(T\). The sparse feasible set is the union, over all sets \(T\) of size at most \(k\), of the unit spheres in those coordinate subspaces. Each individual sphere is simple, but the union has many pieces: there are \(\binom{p}{k}\) possible supports of size \(k\), along with smaller supports.
When \(k<p\), this union is generally nonconvex. For example, if \(k=1\), both coordinate vectors \(e_1\) and \(e_2\) are feasible. Their midpoint \((e_1+e_2)/2\) has norm \(1/\sqrt{2}\), not one, so it is not feasible. More generally, a mixture of feasible loading vectors need not remain in the set: it can violate the unit-norm condition, the sparsity condition, or both. This geometry explains why the problem is not simply an ordinary eigenvector calculation over one spherical feasible region.
The number of possible supports can also be large. This is a structural feature of the constrained problem, not merely a matter of choosing a numerical method. For a small number of variables, one can compare supports exactly; the next results make that calculation precise.
Proof. Fix a nonempty support set \(T\). Any vector \(v\) that is zero outside \(T\) can be written using its coordinates \(v_T\), and it satisfies \(v^\top S v=v_T^\top S_{TT}v_T\) and \(\|v\|_2=\|v_T\|_2\). By the spectral theorem, write \(S_{TT}=Q\Lambda Q^\top\), where \(Q\) is orthogonal and the diagonal entries of \(\Lambda\) are the eigenvalues of \(S_{TT}\). For any unit \(v_T\), putting \(u=Q^\top v_T\) gives $$ v_T^\top S_{TT}v_T =u^\top\Lambda u =\sum_i\lambda_i u_i^2 \le \lambda_{\max}(S_{TT})\sum_i u_i^2 =\lambda_{\max}(S_{TT}). $$ Equality holds by taking \(v_T\) to be a unit eigenvector for the largest eigenvalue. Therefore the maximum over vectors supported within \(T\) is \(\lambda_{\max}(S_{TT})\). Every feasible vector has some nonempty support \(T\) with \(|T|\le k\), and there are finitely many such sets. Maximizing the fixed-support value over those sets proves the result. \(\square\)
The theorem gives an exact finite characterization: sparse PCA can be solved by finding the best support and then computing a largest eigenvalue on that support. It does not say that the support search is easy when \(p\) is large; it identifies what must be compared. For a fixed support, the problem is an ordinary Rayleigh-quotient maximization.
Worked Example: Maximizing Variance on a Fixed Support
Suppose the covariance matrix for two variables is $$ S=\begin{pmatrix}4&2\\2&4\end{pmatrix}. $$ If both variables are allowed, the loading vector must have unit norm. The eigenvectors of \(S\) are proportional to \((1,1)^\top\) and \((1,-1)^\top\), with eigenvalues \(6\) and \(2\), respectively: multiplying \(S\) by these vectors gives \(6(1,1)^\top\) and \(2(1,-1)^\top\).
The largest eigenvalue is \(6\), so the maximum projected variance is \(6\), attained at \(v=(1,1)^\top/\sqrt{2}\) and its negative. Direct substitution checks the value: $$ v^\top S v =\frac{1}{2}(1,1) \begin{pmatrix}4&2\\2&4\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} =\frac{1}{2}(1,1)\begin{pmatrix}6\\6\end{pmatrix} =6. $$ If the support is restricted to the first variable alone, the only unit loadings are \(v=(1,0)^\top\) and its negative, and the variance is \(4\). Thus allowing the second variable increases the attainable projected variance from \(4\) to \(6\).
Special Cases and General Properties
At the sparsest setting, \(k=1\), every feasible vector has exactly one coordinate equal to \(1\) or \(-1\). The objective then depends only on a diagonal entry of \(S\). At the other extreme, \(k=p\) imposes no sparsity restriction, so the maximum is the largest eigenvalue of the full covariance matrix.
Proof. Every unit vector with at most \(k\) nonzero entries also has at most \(k+1\) nonzero entries. Consequently the feasible set for \(k\) is contained in the feasible set for \(k+1\), so maximizing over the larger set cannot give a smaller value. This proves monotonicity. When \(k=1\), a feasible vector is \(e_j\) or \(-e_j\) for some \(j\), so \(v^\top Sv=S_{jj}\); maximizing gives \(\rho_1=\max_j S_{jj}\). When \(k=p\), all unit vectors are feasible, and the spectral theorem gives \(\rho_p=\lambda_{\max}(S)\). Since the feasible set for any \(k\) lies between these two cases, the displayed inequalities follow. \(\square\)
Worked Example: A One-Variable Component
Consider $$ S=\begin{pmatrix}3&1&0\\1&5&0\\0&0&4\end{pmatrix}, $$ and require \(k=1\). The feasible vectors are \(\pm e_1,\pm e_2,\pm e_3\). Their projected variances are \(e_1^\top Se_1=3\), \(e_2^\top Se_2=5\), and \(e_3^\top Se_3=4\); changing the sign does not change any value.
The largest diagonal entry is \(5\), so the sparse optimum is \(v=e_2\) or \(v=-e_2\), with variance \(5\). The off-diagonal covariance \(S_{12}=1\) cannot improve the objective under a one-variable constraint because using both coordinates would violate \(\|v\|_0\le1\). This example illustrates that the available support, not just the numerical size of correlations, determines which directions can be considered.
Worked Example: Comparing Every Support When \(k=2\)
Let $$ S=\begin{pmatrix}4&3&0\\3&4&0\\0&0&5\end{pmatrix} $$ and allow at most two nonzero loadings. The possible supports have size one or two. For the singleton supports, the variances are the diagonal entries \(4,4,5\), so the best singleton value is \(5\).
For support \(\{1,2\}\), the principal submatrix is \(\begin{pmatrix}4&3\\3&4\end{pmatrix}\). Its eigenvectors \((1,1)^\top\) and \((1,-1)^\top\) have eigenvalues \(7\) and \(1\), respectively, so its largest eigenvalue is \(7\). For support \(\{1,3\}\), the principal submatrix is diagonal with entries \(4\) and \(5\), so its largest eigenvalue is \(5\). For support \(\{2,3\}\), the principal submatrix also has diagonal entries \(4\) and \(5\), so its largest eigenvalue is \(5\).
Comparing all these values, the optimum is \(7\), attained by \(v=(1,1,0)^\top/\sqrt{2}\) and its negative. Substitution verifies the objective: $$ v^\top S v =\frac{1}{2}(1,1,0) \begin{pmatrix}7\\7\\0\end{pmatrix} =7. $$ Here the best sparse component uses two variables; neither the best singleton support nor either support involving variable 3 reaches the same variance.
What the Objective Does and Does Not Guarantee
The constrained objective gives a precise trade-off: increasing \(k\) cannot reduce the best achievable projected variance, but the maximizing loading may change abruptly as the allowed support changes. The variance value alone does not establish that the selected variables have a causal or scientific relationship with an outcome. It describes variance in the chosen covariance structure, and interpretation still depends on how the variables were measured and on the study’s aims.
Nor should sparse PCA be interpreted as ordinary PCA followed by thresholding. In the last example, the best two-variable direction emerges from optimizing within each allowed support. In general, zeroing some entries of an unconstrained eigenvector does not preserve its norm or guarantee that the remaining direction maximizes variance on its support.
Common Mistake
- Wrong reasoning: “The sparse solution is just the ordinary first eigenvector with its smallest coordinates set to zero.” That procedure does not compare all admissible supports and need not maximize projected variance under the constraint.
- Correction: The sparse problem optimizes \(v^\top S v\) over unit vectors with at most \(k\) nonzero entries. For a specified support, its optimum is the largest eigenvalue of the corresponding principal submatrix; the global optimum is the largest of those support-specific values.
- Wrong reasoning: “The sparsity constraint is harmless because the objective is still quadratic.” A quadratic objective does not make the feasible set convex.
- Correction: The feasible set is a union of coordinate-subspace spheres. The support restriction is a substantive nonconvex constraint, even though each fixed-support variance maximization has a standard eigenvalue solution.
Check Your Understanding
Use the definitions and support-based characterization to answer these questions.
- For a unit loading vector \(v\), what does \(\|v\|_0\le k\) restrict?
- Why does the sparse feasible set generally fail to be convex when \(k<p\)?
- For a fixed support \(T\), which eigenvalue of \(S_{TT}\) gives the largest attainable projected variance?
- If \(S=\begin{pmatrix}2&0\\0&6\end{pmatrix}\) and \(k=1\), what is the optimal sparse variance and which coordinate achieves it?
- Explain why deleting small entries from an ordinary principal component does not, in general, solve the constrained sparse PCA problem.