High-Dimensional Econometrics · Tutorial 915 of 952

Restricted Eigenvalues and Compatibility Conditions

Learn how restricted eigenvalue and compatibility conditions measure whether correlated designs still provide enough curvature to control sparse estimation error.

Advanced 10 min read

What You'll Learn

Define cone-restricted eigenvalue and compatibility constants for a specified support size and cone.
Interpret why these design conditions matter even when the full design matrix is singular.
Relate compatibility and restricted eigenvalue constants under a common normalization.
Calculate both constants for orthogonal and correlated two-predictor designs.
Recognize when perfect collinearity makes sparse estimation curvature vanish.

Why Curvature Must Be Checked in Sparse Directions

In high-dimensional regression, predictors can be strongly correlated, and the design matrix may be singular when the number of predictors exceeds the sample size. Neither fact alone determines whether sparse coefficient estimation is well behaved. The relevant question is more specific: does the design distinguish coefficient changes in the directions that a sparse estimator can plausibly make? Restricted eigenvalue and compatibility conditions answer this question by measuring the design only on particular cones of coefficient changes.

These are properties of the design matrix, not assumptions about normally distributed errors. They quantify how much the fitted values must change when coefficients move in sparse-relevant directions. If that change is too small, substantially different coefficient vectors can produce nearly identical fitted values, so estimation from the observed outcomes can be unstable.

Model, Normalization, and Cone

Let $y\in\mathbb{R}^n$ be the outcome vector and let $X\in\mathbb{R}^{n\times p}$ be a fixed design matrix. Consider the linear model $y=X\beta_0+u$, where $\beta_0\in\mathbb{R}^p$ is the coefficient vector and $u\in\mathbb{R}^n$ is the error vector. Write $S\subseteq\{1,\ldots,p\}$ for a support set, such as the indices of the nonzero coefficients in $\beta_0$. For any vector $\delta$, $\delta_S$ keeps its entries in $S$ and sets all other entries to zero; $S^c$ is the complement of $S$.

Use the standardization $\|X_j\|_2^2/n=1$ for every column $X_j$, where $\|\cdot\|_2$ is the Euclidean norm. This is the predictor scaling used here to make the constants comparable across columns. The intercept, if present, is treated separately. The definitions below can also be used without standardized columns, but then their numerical values depend on predictor units.

Definition: For a support set $S$ and cone parameter $c>0$, the cone is the set of coefficient changes satisfying $$ \|\delta_{S^c}\|_1\le c\|\delta_S\|_1. $$ It contains changes whose total absolute size outside $S$ is bounded by a multiple of their size inside $S$. The cone includes the zero vector; when taking ratios, definitions exclude $\delta=0$, and the compatibility ratio also requires $\|\delta_S\|_1>0$.

The cone is not a claim that every coefficient error is sparse. Rather, it describes a restricted family of directions in which estimation error often lies. For example, in the Lasso, a basic inequality places the coefficient error in the cone when the empirical score is sufficiently small relative to the penalty. The design conditions below ask whether $X$ has enough curvature on those directions.

Two Design Conditions

Definition: For a given support $S$ and $c>0$, the cone-restricted eigenvalue is $$ \kappa_{\mathrm{RE}}(S,c) = \inf_{\substack{\delta\ne 0\\ \|\delta_{S^c}\|_1\le c\|\delta_S\|_1}} \frac{\|X\delta\|_2}{\sqrt{n}\|\delta\|_2}. $$ The compatibility constant, in the squared convention used here, is $$ \phi^2(S,c) = \inf_{\substack{\|\delta_S\|_1>0\\ \|\delta_{S^c}\|_1\le c\|\delta_S\|_1}} \frac{s\,\|X\delta\|_2^2}{n\|\delta_S\|_1^2}, \qquad s=|S|. $$

Both constants are nonnegative. A positive restricted eigenvalue means that every nonzero cone direction has a fitted-value change bounded below in proportion to its Euclidean coefficient size. A positive compatibility constant means that the fitted-value change is bounded below in proportion to the active coordinates' absolute coefficient size, with the factor $s$ included in the definition. The constants are properties of $X$, $S$, $c$, and the chosen scaling; they are not estimates of a parameter.

For uniform conditions over sparse supports, one considers all $S$ with $|S|\le s$ and takes the smallest corresponding value. In applications, a positive lower bound uniform over those sets is useful because the true support may not be known. A matrix can be singular overall and still have positive cone-restricted constants: directions in its null space need not lie in the relevant cones.

How the Two Constants Relate

The restricted eigenvalue controls Euclidean coefficient error directly, whereas compatibility is tailored to the active-coordinate $L_1$ size. Under the definitions above, a positive restricted eigenvalue implies a positive compatibility constant. The reverse implication also gives a lower bound for the restricted eigenvalue, though that bound may be conservative.

Start with the restricted eigenvalue bound.
For every nonzero cone direction, $\|X\delta\|_2^2/n\ge \kappa_{\mathrm{RE}}^2(S,c)\|\delta\|_2^2$.

Compare the two coefficient norms.
By Cauchy–Schwarz, $\|\delta_S\|_1^2\le s\|\delta_S\|_2^2\le s\|\delta\|_2^2$.

Substitute into the compatibility ratio.
It follows that $s\|X\delta\|_2^2/(n\|\delta_S\|_1^2)\ge\kappa_{\mathrm{RE}}^2(S,c)$; taking the infimum gives $\phi^2(S,c)\ge\kappa_{\mathrm{RE}}^2(S,c)$.

In the other direction, the cone inequality gives $\|\delta\|_2\le\|\delta\|_1\le(1+c)\|\delta_S\|_1$. The definition of compatibility therefore implies $$ \frac{\|X\delta\|_2^2}{n\|\delta\|_2^2} \ge \frac{\phi^2(S,c)}{s(1+c)^2}, \qquad \text{so}\qquad \kappa_{\mathrm{RE}}^2(S,c)\ge \frac{\phi^2(S,c)}{s(1+c)^2}. $$

This comparison is a general bound, not an assertion that the constants are equal. They weight coefficient changes differently, so their actual values can differ substantially, as the examples show.

Worked Example: Orthogonal Predictors

Consider a hypothetical design with $p=3$, standardized orthogonal columns, and Gram matrix $X^\top X/n=I_3$. Let $S=\{1\}$, so $s=1$, and take $c=1$. Write $\delta=(a,b_2,b_3)^\top$. The cone condition is $|b_2|+|b_3|\le |a|$.

Because the columns are orthogonal, $\|X\delta\|_2^2/n=a^2+b_2^2+b_3^2=\|\delta\|_2^2$. Thus every nonzero cone direction has restricted-eigenvalue ratio $1$, giving $\kappa_{\mathrm{RE}}(S,1)=1$.

For compatibility, the ratio is $$ \frac{s\|X\delta\|_2^2}{n\|\delta_S\|_1^2} = \frac{a^2+b_2^2+b_3^2}{a^2} = 1+\frac{b_2^2+b_3^2}{a^2}\ge 1. $$

Equality is attained by $b_2=b_3=0$ and $a\ne0$. Therefore $\phi^2(S,1)=1$. In this design, neither condition loses curvature in the cone.

Worked Example: Strong but Imperfect Correlation

Now take a hypothetical two-predictor design with standardized columns and Gram matrix $$ \frac{X^\top X}{n} = \begin{pmatrix} 1&0.8\\ 0.8&1 \end{pmatrix}. $$ Let $S=\{1\}$, $s=1$, and $c=1$. For $\delta=(a,b)^\top$, the cone is $|b|\le |a|$. When $a\ne0$, set $t=b/a$, so $-1\le t\le1$. The normalized fitted-value energy is $$ \frac{\|X\delta\|_2^2}{na^2}=1+t^2+1.6t. $$

For compatibility, minimize this expression over $[-1,1]$. Completing the square gives $1+t^2+1.6t=(t+0.8)^2+0.36$, whose minimum occurs at $t=-0.8$, inside the cone. Hence $\phi^2(S,1)=0.36$, and $\phi(S,1)=0.600$.

For the restricted eigenvalue, the squared ratio is $$ \frac{\|X\delta\|_2^2}{n\|\delta\|_2^2} = 1+\frac{1.6t}{1+t^2}. $$ Since $2|t|/(1+t^2)\le1$, this ratio is at least $1-0.8=0.20$, with equality at $t=-1$. Therefore $\kappa_{\mathrm{RE}}^2(S,1)=0.20$, or $\kappa_{\mathrm{RE}}(S,1)=0.4472$. The correlated design has positive curvature, but less than the orthogonal design.

The two constants differ: $\phi^2=0.36$, while $\kappa_{\mathrm{RE}}^2=0.20$. The latter is more sensitive here to a direction with a relatively large coefficient change outside $S$, while compatibility scales by the active-coordinate $L_1$ size.

Worked Example: Perfect Collinearity

For a third hypothetical design, let the standardized columns be identical, so $$ \frac{X^\top X}{n} = \begin{pmatrix} 1&1\\ 1&1 \end{pmatrix}. $$ Again take $S=\{1\}$ and $c=1$. The nonzero direction $\delta=(1,-1)^\top$ satisfies the cone condition because $|-1|=|1|$. But $X\delta=X_1-X_2=0$.

Its restricted-eigenvalue ratio is $0/(\sqrt{n}\|\delta\|_2)=0$, so $\kappa_{\mathrm{RE}}(S,1)=0$. Its compatibility ratio is also zero because $\|X\delta\|_2^2=0$ and $\|\delta_S\|_1=1$, giving $\phi^2(S,1)=0$. The data cannot distinguish these coefficient changes through fitted values. A sparse estimator may still select one representation, but this design condition cannot guarantee stable coefficient recovery in the stated cone.

How Curvature Enters Estimation

To see why these conditions matter, consider the Lasso objective $$ \widehat\beta = \arg\min_{\beta\in\mathbb{R}^p} \left\{ \frac{1}{2n}\|y-X\beta\|_2^2+\lambda\|\beta\|_1 \right\}, \qquad \lambda>0. $$ Under $y=X\beta_0+u$, write $\delta=\widehat\beta-\beta_0$. If the score satisfies $\|X^\top u/n\|_\infty\le\lambda/2$, comparing the objective at $\widehat\beta$ and $\beta_0$ gives $$ \frac{\|X\delta\|_2^2}{2n} \le \frac{u^\top X\delta}{n} +\lambda\bigl(\|\beta_0\|_1-\|\beta_0+\delta\|_1\bigr). $$

The score bound makes the first term at most $(\lambda/2)\|\delta\|_1$. Since $\beta_0$ is zero outside $S$, the penalty difference is at most $\|\delta_S\|_1-\|\delta_{S^c}\|_1$. Combining these inequalities yields $$ \frac{\|X\delta\|_2^2}{2n} \le \frac{3\lambda}{2}\|\delta_S\|_1 -\frac{\lambda}{2}\|\delta_{S^c}\|_1. $$ The left side is nonnegative, so $\|\delta_{S^c}\|_1\le3\|\delta_S\|_1$. Thus the error lies in the cone with $c=3$. This short argument explains the role of the cone; KKT conditions provide a complementary characterization of Lasso solutions.

Once the error is known to lie in a cone, a positive compatibility constant or restricted eigenvalue supplies a lower bound on the fitted-value change associated with that error. If the relevant constant is close to zero, a small prediction change can accompany a comparatively large coefficient change. If it is bounded away from zero, the design has enough curvature in the directions the error can take. The resulting quantitative Lasso error bounds are developed using this curvature in the analysis of oracle inequalities.

Common Pitfall and Practical Interpretation

Common pitfall: “The design matrix is singular, so the restricted eigenvalue must be zero.” This is not generally correct. Singularity means some nonzero direction has $X\delta=0$; the restricted eigenvalue is zero only if such a direction is in the specified cone. Conversely, a nonsingular design does not by itself guarantee a useful lower bound: its smallest eigenvalue may be very close to zero.

Always report which support size, cone parameter, and normalization define a condition. A statement that a design “satisfies compatibility” without these details is incomplete. Also distinguish the squared compatibility constant $\phi^2$ used here from conventions that name the unsquared constant $\phi$. The numerical value changes under rescaling of predictors, which is why the column normalization must be stated.

In practice, these conditions formalize a tradeoff: predictors may be correlated, and the full design may have redundant directions, but the design must retain enough curvature on the sparse error cones relevant to the estimator. They are not claims that predictors are uncorrelated, nor do they establish causal interpretation. They are geometric safeguards for relating changes in fitted values to changes in coefficients.

Check Your Understanding

Answer these questions using the definitions and conventions in this tutorial.

For a support $S$, state the cone condition with parameter $c$, and explain why it restricts directions rather than asserting that every vector is sparse.
In the two-predictor design with correlation $0.8$, which value of $t=b/a$ minimizes the compatibility ratio when $S=\{1\}$ and $c=1$?
Why can a singular design matrix still have a positive restricted eigenvalue for a specified cone?
What does a zero compatibility constant imply about the design on the relevant cone?
Explain why predictor standardization matters when comparing numerical values of these constants.

Back to Tutorials