Convex Relaxations for Sparse Principal Components

From Sparse Loadings to a Matrix Optimization

For a sample covariance matrix $S$, the variance along a unit loading vector $v$ is $v^\mathsf{T}Sv$. Sparse principal component analysis seeks a high-variance direction while restricting the number of nonzero entries of $v$. The cardinality restriction makes the problem nonconvex: it requires choosing which variables to retain as well as estimating the loading values.

A useful relaxation starts by replacing the vector with its outer product. This separates the variance objective, which becomes linear in a matrix, from the rank restriction that encodes a single direction. We will then replace the exact sparsity requirement with a convex constraint. The resulting semidefinite program is tractable as a convex optimization problem, but its solutions need not be sparse loading vectors.

Definition: Let $S$ be a symmetric $p\times p$ sample covariance matrix and let $k$ be an integer with $1\leq k\leq p$. The cardinality-constrained sparse principal component problem is $$ \max_{v\in\mathbb{R}^p} v^\mathsf{T}Sv \quad\text{subject to}\quad \|v\|_2=1,\qquad \|v\|_0\leq k, $$ where $\|v\|_0$ is the number of nonzero coordinates of $v$. For a matrix $X$, define its entrywise $\ell_1$ norm by $\|X\|_1=\sum_{i=1}^p\sum_{j=1}^p |X_{ij}|$.

The exact formulation can be lifted by setting $X=vv^\mathsf{T}$. Then $X$ is positive semidefinite, has trace one, and has rank one. Also, $v^\mathsf{T}Sv=\operatorname{tr}(SX)$. If $v$ has at most $k$ nonzero entries, $X$ is zero outside the corresponding rows and columns. The rank-one and support conditions are nonconvex, however, so this lift alone does not solve the problem.

The Entrywise-Norm Relaxation

For a rank-one lift, the entrywise norm has a particularly simple form: $\|vv^\mathsf{T}\|_1=\|v\|_1^2$. If $v$ has at most $k$ nonzero entries, Cauchy–Schwarz gives $\|v\|_1^2\leq k\|v\|_2^2=k$. This motivates replacing the rank-one constraint by a convex norm bound.

Semidefinite relaxation: The standard entrywise-norm relaxation of the cardinality-constrained problem is $$ \max_{X\in\mathbb{R}^{p\times p}}\ \operatorname{tr}(SX) \quad\text{subject to}\quad X\succeq 0,\qquad \operatorname{tr}(X)=1,\qquad \|X\|_1\leq k. $$ Here $X\succeq0$ means that $X$ is symmetric positive semidefinite. The objective is linear, the positive-semidefinite constraint is convex, and the entrywise $\ell_1$ constraint is convex.

Worked Example: Lifting a Two-Variable Component

Take $v=(3/5,4/5,0)^\mathsf{T}$, so that $\|v\|_2^2=9/25+16/25=1$ and $\|v\|_0=2$. Its matrix lift is $$ X=vv^\mathsf{T}= \begin{pmatrix} 9/25&12/25&0\\ 12/25&16/25&0\\ 0&0&0 \end{pmatrix}. $$ It is positive semidefinite because it is an outer product, and its trace is $9/25+16/25=1$.

The entrywise norm is $\|X\|_1=9/25+12/25+12/25+16/25=49/25=1.96\leq2$. Thus the lifted sparse vector is feasible for the relaxation with $k=2$.

For $S=\begin{pmatrix}2&1&0\\1&3&0\\0&0&0\end{pmatrix}$, the vector objective is $v^\mathsf{T}Sv=2(9/25)+2(12/25)+3(16/25)=90/25=3.6$. The matrix objective gives the same value: $\operatorname{tr}(SX)=2(9/25)+2(12/25)+3(16/25)=3.6$. This illustrates how lifting preserves the variance objective exactly.

Why the Relaxed Optimum Is an Upper Bound

Every loading vector allowed by the original problem produces a feasible matrix for the relaxation. The relaxation may admit additional matrices, so it can achieve a larger objective. This inclusion proves the upper-bound property; it does not imply that an optimizer of the relaxation corresponds to any sparse loading vector.

Theorem: If $S$ is symmetric and $1\leq k\leq p$, then the optimal value of the semidefinite relaxation is at least the optimal value of the cardinality-constrained sparse principal component problem.

Proof. Let $v$ be any feasible vector for the cardinality-constrained problem and set $X=vv^\mathsf{T}$. For every $a\in\mathbb{R}^p$, $a^\mathsf{T}Xa=(v^\mathsf{T}a)^2\geq0$, so $X\succeq0$. Also, $\operatorname{tr}(X)=v^\mathsf{T}v=1$, and $\operatorname{tr}(SX)=v^\mathsf{T}Sv$. Finally, if $J$ is the support of $v$, then $$ \|X\|_1=\left(\sum_{i\in J}|v_i|\right)^2 \leq |J|\sum_{i\in J}v_i^2 \leq k. $$ Thus $X$ is feasible for the relaxation and has the same objective value as $v$. Since this holds for every feasible $v$, maximizing over the larger relaxed feasible set cannot give a smaller value. $\square$

The relaxed problem has an optimizer: its feasible set is nonempty, closed, and bounded. To see boundedness, a positive semidefinite matrix with trace one has nonnegative eigenvalues summing to one, hence $\|X\|_F\leq1$. The objective is continuous, so it attains its maximum on this compact set. This existence fact makes the comparison of optimal values well-defined.

A Relaxation Can Admit a Nonsparse Direction

The norm bound controls the total size of the matrix entries; it does not impose an exact limit on the number of nonzero coordinates in a loading vector. Further, a feasible $X$ need not have rank one at all. Its interpretation may therefore be a matrix solution to the relaxed problem, not a single principal component.

Worked Example: A Strict Gap Between the Relaxation and the Sparse Problem

Let $v=(\sqrt{0.98},0.1,0.1)^\mathsf{T}$, which has unit norm, and take $S=vv^\mathsf{T}$ with $k=2$. The matrix $S$ is positive semidefinite and has largest eigenvalue $1$. The relaxed problem can use $X=vv^\mathsf{T}$. Its norm is $$ \|X\|_1=(\sqrt{0.98}+0.2)^2 =0.98+0.4\sqrt{0.98}+0.04 \approx1.416<2. $$ It is feasible, and its objective is $\operatorname{tr}(SX)=\operatorname{tr}(vv^\mathsf{T}vv^\mathsf{T})=(v^\mathsf{T}v)^2=1$. No feasible relaxed matrix can have a larger objective: for any $X\succeq0$ with trace one, $\operatorname{tr}(SX)=v^\mathsf{T}Xv\leq\operatorname{tr}(X)=1$, since $X\succeq0$ and $\|v\|_2=1$. Thus the relaxed optimum is $1$.

For a unit vector $x$ supported on a set $J$ of size at most two, the Cauchy–Schwarz inequality gives $(v^\mathsf{T}x)^2=(v_J^\mathsf{T}x_J)^2\leq\|v_J\|_2^2$. The largest possible $\|v_J\|_2^2$ is $0.98+0.01=0.99$, attained by retaining the first coordinate and either of the other two. Choosing $x$ proportional to $v_J$ attains this bound. Since $x^\mathsf{T}Sx=(v^\mathsf{T}x)^2$, the cardinality-constrained optimum is exactly $0.99$, strictly less than the relaxed optimum $1$. Here the relaxed feasible matrix corresponds to a direction with three nonzero coordinates, which the original problem forbids.

This example shows why a relaxed value is often best understood as an upper bound, not as a guarantee that the original sparse optimum has been recovered. To obtain a loading vector for interpretation, an analyst may need a separate extraction or rounding step and should evaluate the resulting vector under the original cardinality constraint.

Penalized Formulations and Multipliers

A related convex formulation places a penalty on the entrywise norm instead of imposing an upper bound: $$ \max_{X\succeq0,\ \operatorname{tr}(X)=1} \left\{\operatorname{tr}(SX)-\lambda\|X\|_1\right\}, \qquad \lambda\geq0. $$ This objective is concave in $X$, because it is linear minus a convex function. Consequently, maximizing it over the convex positive-semidefinite trace-one set is a convex optimization problem. The penalty discourages large entrywise norms, but it does not directly count nonzero loadings.

Worked Example: How a Norm Penalty Changes a Two-Variable Solution

Consider $S=\begin{pmatrix}1&0.8\\0.8&1\end{pmatrix}$, which is positive semidefinite, and a positive-semidefinite trace-one matrix $X=\begin{pmatrix}a&b\\b&1-a\end{pmatrix}$. Positive semidefiniteness requires $0\leq a\leq1$ and $b^2\leq a(1-a)$, so in particular $|b|\leq1/2$. The objective and penalty norm are $\operatorname{tr}(SX)=1+1.6b$ and $\|X\|_1=1+2|b|$.

Because the coefficient of $b$ in the variance objective is positive, a maximizer can take $b\geq0$. The penalized objective is then $1-\lambda+1.6b-2\lambda b=1-\lambda+2(0.8-\lambda)b$. Every $b\in[0,1/2]$ is feasible by choosing $a=1/2$. If $\lambda=0.5$, the coefficient of $b$ is $0.6>0$, so the maximum uses $b=1/2$. This gives $X=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}$, with objective $1.8$, norm $2$, and penalized value $1.8-0.5(2)=0.8$. At $b=0$, the penalized value is only $1-0.5=0.5$.

If $\lambda=0.9$, the coefficient of $b$ is $-0.2$, so $b=0$ maximizes the penalized objective. Its value is $1-0.9=0.1$; the choice $b=1/2$ gives $1.8-0.9(2)=0$. In this example, increasing the penalty removes the off-diagonal entry. This is a matrix-level effect, and should not be confused with an exact count of nonzero entries in a loading vector.

For the norm-constrained relaxation, a multiplier interpretation requires care. Let $C=\{X\succeq0:\operatorname{tr}(X)=1\}$. If $k>1$, the constraint $\|X\|_1\leq k$ satisfies Slater’s condition: $I/p$ is positive definite, has trace one, and has norm one, strictly less than $k$. The Karush–Kuhn–Tucker conditions therefore give, at an optimum $X^\star$, a multiplier $\lambda\geq0$ satisfying complementary slackness $\lambda(\|X^\star\|_1-k)=0$, together with the stationarity condition for maximizing $\operatorname{tr}(SX)-\lambda\|X\|_1$ over $C$. Equivalently, $X^\star$ maximizes that penalized objective over $C$. These conditions describe a connection between the constrained and penalized formulations under the stated regularity condition; they do not assert a one-to-one correspondence for every penalty value.

Multiplier takeaway: If the KKT multiplier is positive, complementary slackness forces $\|X^\star\|_1=k$, so the norm constraint is active. A zero multiplier does not force the constraint to be slack: it may be slack or active. Conversely, an active constraint can have a zero multiplier.

Multiple Components and Practical Interpretation

For a rank-$r$ subspace, an orthonormal loading matrix $U$ gives the projection $P=UU^\mathsf{T}$, with $P\succeq0$, $\operatorname{tr}(P)=r$, and $P^2=P$. The variance captured by the subspace is $\operatorname{tr}(SP)$. Dropping the nonconvex idempotence condition leads to the Fantope $0\preceq H\preceq I,\ \operatorname{tr}(H)=r$. A possible convex sparsity surrogate is $\|H\|_1\leq rk$: if the projection is supported on at most $k$ variables, then $\|P\|_1\leq(\sum_i\sqrt{P_{ii}})^2\leq k\sum_iP_{ii}=kr$. This is again a relaxation, not an exact support condition.

Convex relaxations are useful because they replace a combinatorial search with optimization over a convex set and provide an objective bound against which approximate solutions can be assessed. But the choice of surrogate affects what is controlled: the matrix norm is not the vector cardinality, and a positive-semidefinite matrix may combine several directions rather than identify one loading. In applications, report the relaxation, any method used to extract sparse loadings, and the variance those loadings actually achieve.

Common Mistakes

Treating the norm bound as an exact support constraint. A bound on $\|X\|_1$ controls aggregate magnitude; it does not ensure that only $k$ variables are used.
Assuming every feasible matrix is a component. The relaxation drops the rank-one condition, so a feasible $X$ may not equal $vv^\mathsf{T}$ for any vector $v$.
Calling the relaxed optimum the sparse optimum. Feasible-set inclusion proves an upper bound. The gap example shows that the bound can be strict.
Inferring activity from a zero multiplier. Complementary slackness forces activity when the multiplier is positive, but a zero multiplier permits either an active or slack constraint.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

For a unit vector with at most $k$ nonzero coordinates, why is the entrywise norm of its outer product at most $k$?
Which nonconvex feature of the exact matrix lift is removed in the semidefinite relaxation?
Why does the relaxed optimal value bound the cardinality-constrained value from above?
Can an optimizer of the relaxation always be interpreted as a single loading vector? Explain.
What does complementary slackness imply when the norm-constraint multiplier is positive, and what does it not imply when the multiplier is zero?