Restricted eigenvalue and irrepresentable condition: Definition & Examples

The restricted eigenvalue (RE) condition requires a regression design to retain curvature along specified sparse-error directions. The irrepresentable condition limits how strongly inactive predictors mimic a signed combination of active predictors. They address different questions: controlling Lasso estimation error and recovering the exact variables, respectively. A quant can obtain a useful return forecast without correctly identifying which candidate signals generated it.

Fix the model and the normalisation

Take the correctly specified linear regression model

y=X\beta^*+\varepsilon,\qquad \hat\beta\in\arg\min_{b\in\mathbb R^p} \left\{\frac{1}{2n}\lVert y-Xb\rVert_2^2+\lambda\lVert b\rVert_1\right\},\quad \lambda>0.

Here

X

is a fixed

n\times p

design,

S=\{j:\beta_j^*\ne0\}

is the true active set and

s=|S|\ge1

. The intercept has been removed by centring; each column satisfies

\lVert X_j\rVert_2^2/n=1

. Thus the normalised Gram matrix

G=X^\top X/n

has diagonal entries one. These are statements about the design used in the fit, not an assumed population correlation matrix. The L1 penalty uses the displayed loss scale.

Write $\delta=\hat\beta-\beta^*$ . Three distinct targets are:

Target	What is controlled or recovered?
Empirical prediction error	$\lVert X\delta\rVert_2^2/n$ , on the observed design
Coefficient error	A norm such as $\lVert\delta\rVert_1$
Exact signed support	$\operatorname{sign}(\hat\beta)=\operatorname{sign}(\beta^*)$ , with $\operatorname{sign}(0)=0$

Exact signed support requires every inactive coefficient to be exactly zero. Small coefficient error can still leave tiny false positives.

Restricted curvature: on which cone?

For a specified $S$ and finite $c>0$ , define

\mathcal C(S,c)=\{\delta:\lVert\delta_{S^c}\rVert_1\le c\lVert\delta_S\rVert_1\},\qquad \kappa(S,c)=\inf_{\substack{\delta\in\mathcal C(S,c)\\delta\ne0}} \frac{\sqrt{\delta^\top G\delta}}{\lVert\delta_S\rVert_2}.

The cone bounds off-support error relative to on-support error. RE holds here when $\kappa(S,c)>0$ . A nonzero cone vector has a nonzero denominator. A uniform RE condition minimises this constant over all nonempty sets with size at most

s

; specifying only one support is a different assumption. Authors also use other denominator conventions, so constants must be compared with their definitions.

For this Lasso objective, the basic inequality gives $\delta\in\mathcal C(S,3)$ on the noise-score event

\left\lVert\frac{X^\top\varepsilon}{n}\right\rVert_\infty\le\frac{\lambda}{2}.

With sparsity and suitable positive RE, this leads to prediction and coefficient-error bounds. Noise assumptions and penalty choice determine the event's probability; RE alone does not supply that probability. When

p>n

G

is singular, yet restricted curvature can remain positive because the cone can exclude its nonzero null directions. See Bickel, Ritov and Tsybakov, §3 and Theorem 7.2.

Signed separation: can inactive variables stay out?

Assume $G_{SS}$ is invertible and let $z_S=\operatorname{sign}(\beta_S^*)$ . A strict, sign-specific irrepresentable condition with margin is

\left\lVert G_{S^cS}G_{SS}^{-1}z_S\right\rVert_\infty\le1-\eta, \qquad \eta>0.

It measures how active-variable shrinkage spills into inactive-variable scores. It depends on the active signs, not just pairwise correlations or eigenvalues. For an asymptotic sequence, a uniform positive margin is stronger than merely being below one separately at each sample size.

Exact recovery also needs active signals large enough relative to noise and shrinkage, and appropriate tuning and design assumptions. The condition alone is not a finite-sample recovery guarantee. Zhao and Yu, §2–2.1, distinguish estimation consistency from signed-support consistency and state the regularity assumptions for their results.

One design passes curvature and fails separation

Consider this synthetic three-predictor Gram matrix:

G=\begin{pmatrix} 1&0&0.6\\ 0&1&0.6\\ 0.6&0.6&1 \end{pmatrix}.

Its eigenvalues are

1

and

1\pm\sqrt{0.72}

. The smallest is approximately

0.15147186

, so

G

is positive definite. For every

\delta

\delta^\top G\delta\ge0.15147186\lVert\delta\rVert_2^2 \ge0.15147186\lVert\delta_S\rVert_2^2.

Consequently RE holds on every specified cone, with $\kappa(S,c)^2\ge1-\sqrt{0.72}$ . This is a lower bound, not a calculation of the exact cone minimum.

Now take $\beta^*=(1,1,0)^\top$ . Then $S=\{1,2\}$ , $G_{SS}=I_2$ and $z_S=(1,1)^\top$ . The inactive score is

\left|(0.6,0.6)I_2^{-1}\begin{pmatrix}1\\1\end{pmatrix}\right|=1.2>1.

The strict condition fails. Changing the active signs to $(1,-1)$ would make this score zero: the design alone does not specify the signed condition.

Synthetic three-predictor design: minimum Gram eigenvalue 0.151472 is positive, while two signed contributions of 0.6 sum to an irrepresentable score of 1.2, above the strict boundary of one. At lambda 0.1, true coefficients (1, 1, 0) produce fitted coefficients approximately (0.857143, 0.857143, 0.071429).

Original dimensionless, noiseless example. Positive curvature controls errors but does not force the inactive coefficient to stay zero; the third predictor enters the unique Lasso fit.

The failure has a concrete consequence even without noise. Suppose a Lasso solution kept coefficient 3 at zero and coefficients 1 and 2 positive. Its active optimality equations would give $\hat\beta_S=\beta_S^*-\lambda(1,1)^\top$ . The inactive residual score would then be $1.2\lambda$ . But keeping coefficient 3 at zero requires its absolute residual score to be at most $\lambda$ , by the Karush–Kuhn–Tucker conditions. Those requirements conflict for every $\lambda>0$ .

For example, at $\lambda=0.1$ , direct solution of the optimality equations gives the unique fit

\hat\beta=\left(\frac67,\frac67,\frac1{14}\right)^\top \approx(0.857143,0.857143,0.071429)^\top.

All three entries are positive and satisfy $G(\hat\beta-\beta^*)=-0.1(1,1,1)^\top$ . Positive definiteness makes the objective strictly convex, so these optimality equations certify the unique minimiser. Its coefficient L2 error is $3/14\approx0.214286$ and its empirical squared prediction error is $3/140\approx0.021429$ ; nevertheless it includes a false positive. These are dimensionless quantities from a constructed example, not measured forecast performance.

This full-rank

3\times3

Gram can be realised by a centred design with four observations. It demonstrates a logical separation of conditions; it does not establish performance in the

p>n

regime.

For factor research, decide whether the intended claim concerns prediction or identifying the exact active signals. Multicollinearity can complicate either task, but a forecast-error result does not certify the selected factor list. Unknown true support and signs also prevent treating the displayed irrepresentable score as a routine observable diagnostic.

For penalty mechanics and correlated-predictor behaviour, see Ridge, Lasso, and Elastic Net (membership; public preview).

Sources

Bickel, Ritov and Tsybakov (2009), Simultaneous analysis of Lasso and Dantzig selector, §3, Theorem 7.2 and Appendix B: restricted cones, RE conventions and error control under explicit noise and tuning assumptions.
Zhao and Yu (2006), On Model Selection Consistency of Lasso, §2–2.1: signed irrepresentability, margins and the distinction between estimation and selection consistency.

Fix the model and the normalisation

Restricted curvature: on which cone?

Signed separation: can inactive variables stay out?

One design passes curvature and fails separation

Sources

Related terms

Eigenvalue

L1 regularization

Linear regression

Positive definite matrix