Compatibility condition
Definition. For a design matrix \(X\) and support \(S\), the compatibility constant \(\phi_0(S)\) is the largest number such that \[ {\|X\Delta\|_2^2\over n}\ge {\phi_0(S)^2\|\Delta_S\|_1^2\over |S|} \] for all \(\Delta\) in the cone \(\|\Delta_{S^c}\|_1\le3\|\Delta_S\|_1\).
Proposition. The compatibility condition is weaker than a restricted eigenvalue lower bound in \(\ell_2\), but it is exactly matched to \(\ell_1\)-oracle inequalities for the Lasso.
Proof. On the cone, \(\|\Delta_S\|_1\le\sqrt{|S|}\|\Delta_S\|_2\). A restricted eigenvalue bound controlling \(\|\Delta_S\|_2\) therefore implies the displayed compatibility bound. The converse need not hold because compatibility controls only the active \(\ell_1\) size.
Irrepresentability
Definition. For Gram matrix \(\Sigma=X^\top X/n\), the irrepresentable condition for signed support recovery is \[ \|\Sigma_{S^cS}\Sigma_{SS}^{-1}\operatorname{sign}(\beta_S^*)\|_\infty\le1-\eta \] for some \(\eta>0\).
Theorem. In the noiseless KKT geometry of Lasso, exact signed support recovery requires the inactive gradients to be strictly inside the subgradient cube. This is encoded by the irrepresentable condition plus a beta-min lower bound.
Proof. Assume the active solution is known. The KKT equations solve the active coordinates and impose \(\|X_{S^c}^\top(y-X_S\hat\beta_S)/n\|_\infty\le\lambda\) on inactive coordinates. Substituting the active solution gives a deterministic leakage term \(\Sigma_{S^cS}\Sigma_{SS}^{-1}\operatorname{sign}(\beta_S^*)\). Strict containment leaves room for noise; beta-min prevents active coefficients from being shrunk through zero.
Basic inequality for the Lasso
Theorem. In \(y=X\beta^*+\varepsilon\), if \(\lambda\ge2\|X^\top\varepsilon/n\|_\infty\), then the Lasso error \(\Delta=\hat\beta-\beta^*\) satisfies \(\|\Delta_{S^c}\|_1\le3\|\Delta_S\|_1\) and \[ {1\over n}\|X\Delta\|_2^2+\lambda\|\Delta\|_1\lesssim \lambda\|\Delta_S\|_1. \]
Proof. Compare the penalized objective at \(\hat\beta\) and \(\beta^*\). The stochastic term is bounded by \(\lambda\|\Delta\|_1/2\). Rearranging separates active and inactive coordinates and yields the cone condition and inequality.
A hierarchy of design conditions
Proposition. For a fixed support \(S\), the following implications hold, with appropriate constants: \[ \text{uniform sparse eigenvalue} \Longrightarrow\text{restricted eigenvalue} \Longrightarrow\text{compatibility}. \] Irrepresentability is generally incomparable with restricted eigenvalues: it controls leakage from active to inactive variables rather than prediction curvature on a cone.
Proof. A uniform lower eigenvalue bound on all vectors of support size proportional to \(|S|\) extends to the cone by decomposing \(\Delta_{S^c}\) into decreasing coordinate blocks. Restricted eigenvalues give \(\|X\Delta\|/\sqrt n\ge\kappa\|\Delta_S\|_2\), and \(\|\Delta_S\|_1\le\sqrt{|S|}\|\Delta_S\|_2\) yields compatibility. For incomparability, correlated inactive variables can violate irrepresentability while the Gram matrix remains well conditioned on sparse cones; conversely, an active block can be nearly singular even when its projection onto inactive variables is small.
Primal-dual witness construction
Theorem. Let \(Y=X_S\beta_S^*+\varepsilon\), and suppose \(\Sigma_{SS}\) is invertible. Construct \[ \widetilde\beta_{S} =\beta_S^*+ \Sigma_{SS}^{-1} \left(\frac{X_S^\top\varepsilon}{n} -\lambda z_S\right), \qquad \widetilde\beta_{S^c}=0, \] where \(z_S=\operatorname{sign}(\beta_S^*)\). Define \[ \widetilde z_{S^c} =\Sigma_{S^cS}\Sigma_{SS}^{-1}z_S+ \frac1\lambda \left[ \frac{X_{S^c}^\top\varepsilon}{n} -\Sigma_{S^cS}\Sigma_{SS}^{-1} \frac{X_S^\top\varepsilon}{n} \right]. \] If \(\|\widetilde z_{S^c}\|_\infty<1\) and \(\operatorname{sign}(\widetilde\beta_S)=z_S\), then \(\widetilde\beta\) is the unique Lasso solution and recovers the signed support.
Proof. The Lasso KKT equations are \[ \frac{X^\top(Y-X\beta)}{n}=\lambda z, \quad z_j=\operatorname{sign}(\beta_j)\text{ if }\beta_j\ne0, \quad |z_j|\le1\text{ otherwise}. \] The displayed active solution solves the \(S\)-coordinates. Substitution into the inactive score gives exactly \(\widetilde z_{S^c}\). Strict dual feasibility and active sign agreement verify all KKT conditions. Invertibility on \(S\) and strict complementarity rule out a second fitted active solution.
How irrepresentability leaves room for noise
Corollary. If \[ \|\Sigma_{S^cS}\Sigma_{SS}^{-1}z_S\|_\infty\le1-\eta \] and the projected-noise term in \(\widetilde z_{S^c}\) has sup norm at most \(\eta\lambda\), then dual feasibility holds, strictly if one inequality is strict.
Proof. Apply the triangle inequality to the deterministic leakage and projected-noise terms defining \(\widetilde z_{S^c}\).
The beta-min threshold
Proposition. Active sign recovery follows if \[ \min_{j\in S}|\beta_j^*| > \left\| \Sigma_{SS}^{-1} \left(\frac{X_S^\top\varepsilon}{n}-\lambda z_S\right) \right\|_\infty. \] A sufficient deterministic condition is \[ \beta_{\min}> \|\Sigma_{SS}^{-1}\|_{\infty} \left(\left\|\frac{X_S^\top\varepsilon}{n}\right\|_\infty+\lambda\right). \]
Proof. The active-coordinate perturbation is the vector added to \(\beta_S^*\) in the primal-dual witness. If every perturbation coordinate is smaller in magnitude than the corresponding signal, no coordinate crosses zero. The matrix-norm inequality gives the sufficient condition.
Necessity for sign consistency
Theorem. In a fixed-design asymptotic regime, if Lasso achieves signed support recovery with probability tending to one and the normalized noise vanishes relative to \(\lambda\), then the weak irrepresentable condition \[ \|\Sigma_{S^cS}\Sigma_{SS}^{-1} \operatorname{sign}(\beta_S^*)\|_\infty\le1 \] is necessary.
Proof. On the sign-recovery event, solve the active KKT equation for the active estimation error and substitute it into the inactive KKT inequality. Divide by \(\lambda\). The normalized stochastic terms vanish by assumption, leaving the deterministic inequality in the limit.
Mutual incoherence as a transparent sufficient condition
Proposition. Suppose columns are normalized and \[ \mu=\max_{j\ne k}|\Sigma_{jk}|. \] If \((2s-1)\mu<1\), every \(s\)-sparse representation is unique. Stronger numerical margins on \(s\mu\) imply restricted-eigenvalue and irrepresentability bounds.
Proof. Gershgorin's theorem places eigenvalues of a \(k\times k\) principal block in \([1-(k-1)\mu,1+(k-1)\mu]\). If two \(s\)-sparse representations agreed, their \(2s\)-sparse difference would lie in the null space of a positive-definite \(2s\)-column Gram block, a contradiction.
Prediction, screening, and exact recovery
The following targets are progressively stronger:
- prediction consistency of \(X\widehat\beta\);
- estimation consistency in \(\ell^1\) or \(\ell^2\);
- screening, \(S\subseteq\widehat S\);
- support recovery, \(\widehat S=S\);
- signed support recovery.
Prediction may remain possible with identical columns, whereas support recovery is then unidentifiable. Each stronger target needs a correspondingly stronger design and signal condition; a prediction theorem cannot be reported as a variable-selection theorem.