Why High-Dimensional Lasso Needs Careful Interpretation
In a high-dimensional design, the number of candidate predictors \(p\) exceeds the number of observations \(n\). Ordinary least squares cannot uniquely determine all coefficients in this setting: the design matrix has a nontrivial null space. Lasso can still produce a fit by penalizing the sum of the absolute coefficient values. The penalty often gives a sparse solution, but the number of selected predictors is not governed by a simple unconditional rule.
The key distinctions are between a sparse solution that exists, a unique coefficient solution, and the number of nonzero coefficients in every solution. These are not equivalent claims. Rank limits how many predictors are needed to represent an optimal fit, while special design structure can allow other optimal coefficient vectors with more nonzero entries.
This objective uses a penalty parameter \(\lambda\) and an average squared-error term. If an intercept is included but not penalized, it can be handled separately; after centering the response and predictors, the formulas below apply to the centered design. Predictor scaling matters because the penalty acts on coefficient magnitudes, so comparisons of selection counts assume the chosen scaling has been considered.
How Rank Constrains a Sparse Representation
The rank \(r=\operatorname{rank}(X)\) is at most \(n\), and may be smaller if rows or columns are linearly dependent. Lasso has an important high-dimensional property: an optimal fit can be represented using at most \(r\) predictors. Under the usual general-position condition on the columns of the design (considered in their span), the coefficient solution is unique, so its support also has size at most \(r\), and therefore at most \(n\).
General position excludes particular degeneracies in which several signed predictor columns can tie in the optimality conditions. The condition is sufficient for uniqueness, not a description of every real data set. If it fails, a sparse solution still exists, but there may also be other optimal coefficient vectors with more nonzero entries.
The rank bound can be justified using the lasso optimality conditions. Write the residual as \(e=y-X\beta\). For each nonzero coefficient, the Karush–Kuhn–Tucker (KKT) condition is \(\frac{1}{n}X_j^\mathsf{T}e=\lambda\operatorname{sign}(\beta_j)\). For a zero coefficient, the condition is \(\left|\frac{1}{n}X_j^\mathsf{T}e\right|\le\lambda\).
Here is why these conditions imply that a sparse representation exists. If \(\beta\ne 0\), let \(t=\|\beta\|_1\). For every active predictor, its signed column \(\operatorname{sign}(\beta_j)X_j\) satisfies \(\frac{1}{n}e^\mathsf{T}\operatorname{sign}(\beta_j)X_j=\lambda\). Also, \(X\beta/t\) is a weighted average of these signed columns, with nonnegative weights \(|\beta_j|/t\) that sum to one. The signed columns lie in the \(r\)-dimensional span of \(X\) and in a hyperplane, so their affine dimension is at most \(r-1\). Carathéodory’s theorem says that a point in their convex hull can be written as a weighted average of at most \(r\) of them. Using those weights gives a coefficient vector with the same fitted values and the same \(\ell_1\) norm, hence the same objective, and with at most \(r\) nonzero coefficients. If \(\beta=0\), the bound holds immediately.
The fitted values are unique even when the coefficients are not. If two minimizers had different fitted vectors, their midpoint would have strictly smaller squared-error loss, while the convexity of the \(\ell_1\) penalty means its penalty could be no larger than the average penalty. That would contradict optimality. Different coefficient vectors can nevertheless give the same fitted values when \(X\) has a nontrivial null space.
Worked Calculations in High-Dimensional Designs
Worked Example: Verifying a One-Predictor Fit When \(p>n\)
There are \(n=2\) observations and \(p=4\) predictors. Let the columns of \(X\) be \(X_1=(1,0)^\mathsf{T}\), \(X_2=(0,1)^\mathsf{T}\), \(X_3=(1,1)^\mathsf{T}\), and \(X_4=(1,-1)^\mathsf{T}\), with \(y=(2,1)^\mathsf{T}\). For \(\lambda=0.75\), verify the proposed lasso solution \(\hat\beta=(0,0,0.75,0)^\mathsf{T}\). State the method and identify the trap it avoids.
Method: check the KKT conditions. The proposed fitted vector is \(X\hat\beta=0.75(1,1)^\mathsf{T}=(0.75,0.75)^\mathsf{T}\), so the residual is \(e=y-X\hat\beta=(1.25,0.25)^\mathsf{T}\).
For the active third predictor, \(\frac{1}{2}X_3^\mathsf{T}e=(1.25+0.25)/2=0.75=\lambda\), as required for a positive coefficient. For the inactive predictors, the corresponding values are \(\frac{1}{2}X_1^\mathsf{T}e=0.625\), \(\frac{1}{2}X_2^\mathsf{T}e=0.125\), and \(\frac{1}{2}X_4^\mathsf{T}e=(1.25-0.25)/2=0.5\). Each absolute value is at most \(0.75\), so all KKT conditions hold. Convexity of the objective makes these conditions sufficient for optimality.
As a check, the squared residual norm is \(1.25^2+0.25^2=1.625\). The objective value is \(1.625/(2\cdot2)+0.75(0.75)=0.40625+0.5625=0.96875\). The value at \(\beta=0\) is \((2^2+1^2)/4=1.25\), which is larger. The trap is to assume that having four predictors and two observations prevents a sparse lasso fit; this verified optimum uses just one predictor.
Worked Example: Reaching the Rank Bound
Let \(n=3\), \(p=5\), and let the columns of \(X\) be \(X_1=(1,0,0)^\mathsf{T}\), \(X_2=(0,1,0)^\mathsf{T}\), \(X_3=(0,0,1)^\mathsf{T}\), \(X_4=(1,-1,0)^\mathsf{T}\), and \(X_5=(0,1,-1)^\mathsf{T}\). With \(y=(4,3,2)^\mathsf{T}\) and \(\lambda=1/3\), verify the proposed solution \(\hat\beta=(3,2,1,0,0)^\mathsf{T}\).
Method: use rank and KKT checks. The first three columns are the identity vectors, so \(\operatorname{rank}(X)=3\). The proposed fit is \(X\hat\beta=(3,2,1)^\mathsf{T}\), giving residual \(e=(1,1,1)^\mathsf{T}\).
For the three active predictors, the normalized inner products with the residual are each \(1/3\). Their coefficients are positive, so each satisfies the active KKT condition. For the fourth and fifth predictors, the inner products are \(1-1+0=0\) and \(0+1-1=0\); after division by \(n=3\), both are zero and thus have absolute value no larger than \(\lambda\). The proposed vector is therefore optimal.
Its support has size three, equal to the rank and to \(n\), despite \(p=5\). The objective is \(\|e\|_2^2/(2n)+\lambda\|\hat\beta\|_1=3/6+(1/3)(3+2+1)=0.5+2=2.5\). The trap is to confuse \(p>n\) with a requirement that the lasso select fewer than \(n\) predictors. The rank bound allows \(n\) active predictors when the design has rank \(n\).
Worked Example: Duplicate Predictors Can Give a Larger Support
Take \(n=2\), \(p=3\), with columns \(X_1=(1,0)^\mathsf{T}\), \(X_2=(0,1)^\mathsf{T}\), and \(X_3=(1,0)^\mathsf{T}\). Let \(y=(3,2)^\mathsf{T}\) and \(\lambda=0.5\). Compare \(\hat\beta^{(a)}=(2,1,0)^\mathsf{T}\) and \(\hat\beta^{(b)}=(1,1,1)^\mathsf{T}\).
Method: compare fits, penalties, and KKT conditions. Both coefficient vectors produce the fit \((2,1)^\mathsf{T}\), because \(X_1=X_3\). Both have \(\ell_1\) norm \(3\). Their common residual is \(e=(1,1)^\mathsf{T}\); the normalized inner products with all three columns are \(0.5\). For every positive active coefficient the KKT value equals \(+\lambda\); any inactive coefficient also satisfies the absolute-value bound. Thus both vectors are optimal.
The common objective is \((1^2+1^2)/4+0.5(3)=0.5+1.5=2.0\). The first vector has two nonzero coefficients, while the second has three, more than \(n=2\). The trap is to apply the “at most \(n\)” statement to every optimal coefficient vector regardless of design. Exact duplicate predictors violate the needed nondegeneracy; here the fit is unchanged as coefficient weight is shared between the duplicates.
What the Support Bound Does—and Does Not—Say
When \(p>n\), there are more coefficient coordinates than the data can independently identify. Lasso’s \(\ell_1\) penalty favors solutions that use fewer coordinates, and the rank result guarantees that an optimal fit can be represented sparsely. Under general position, uniqueness makes that sparse representation the coefficient solution. These are useful structural facts, but they do not imply that the selected variables are necessarily the “true” predictors or that selection is stable under changes to the data.
For an unpenalized intercept, centering can reduce the effective rank further. The centered design has at most \(n-1\) independent columns because its columns lie in the subspace orthogonal to the all-ones vector. Thus a rank-based bound after centering may be \(n-1\), or lower, rather than \(n\). Always state which design matrix is being ranked and whether the intercept has been separated.
| Design situation | Safe conclusion about support |
|---|---|
| Rank \(r\), arbitrary design, \(\lambda>0\) | There exists an optimal solution with at most \(r\) nonzero coefficients. |
| Usual general-position condition | The coefficient solution is unique and has at most \(r\le n\) nonzero coefficients. |
| Degenerate or duplicate columns | There may be multiple coefficient solutions; some may have more than \(n\) nonzero entries. |
| Unpenalized intercept with centered predictors | Use the rank of the centered design; it is at most \(n-1\). |
The practical exam-style question is therefore not just “Is \(p\) greater than \(n\)?” It is also “What is the rank, and are the coefficient solution and design sufficiently nondegenerate for the support bound to apply to the solution itself?” This distinction is aligned with the SOA Exam PA (Predictive Analytics) syllabus.
- Do not infer uniqueness from sparsity. A sparse solution may coexist with a denser coefficient representation of the same fit.
- Do not state an unconditional support limit. The rank bound guarantees a sparse optimal representation; the bound for every optimal coefficient vector needs uniqueness conditions.
- Do not confuse \(p\) with rank. A design can have many columns but low rank, and the effective bound is based on rank.
- Do not ignore the intercept convention. Centering can change the rank relevant to the support bound.
Check Your Understanding
For each problem, focus on the distinction between predictor count, rank, and coefficient uniqueness.
- A design has \(n=6\), \(p=11\), and rank \(4\). For \(\lambda>0\), what maximum support size is guaranteed for at least one optimal solution? (Answer: 4)
- A design has \(n=5\), \(p=8\), and rank \(5\), with columns in general position. What is the maximum number of nonzero coefficients in its unique lasso solution? (Answer: 5)
- A design has two identical columns and admits two optimal coefficient vectors with the same fit, one supported on two columns and one on four. Does this contradict the rank-based existence result, and why? (Answer: No; the result guarantees an optimal solution with support no larger than the rank, not that every solution is sparse.)
- There are \(n=7\) observations, an unpenalized intercept, and a centered predictor matrix of rank \(5\). Under general position in the centered design, what support bound applies to the unique lasso coefficient vector? (Answer: At most 5 predictors.)
- For \(n=3\), the residual is \(e=(2,1,0)^\mathsf{T}\), and a candidate positive active predictor is \(X_j=(1,1,0)^\mathsf{T}\). With objective \(\|y-X\beta\|_2^2/(2n)+\lambda\|\beta\|_1\) and \(\lambda=0.5\), does this predictor satisfy the active KKT condition? (Answer: Yes; \(X_j^\mathsf{T}e/n=(2+1)/3=1\) — correction: no, it does not equal \(0.5\), so the candidate fails the active KKT condition.)