I am new on this web-site and coming from the field of economics (although interested in High Dimensional Statistics), I am reading Statistics for High Dimensional Data of Bühlmann and Van De Geer. I struggle to get an intuition of what is the compatibility constant. As far as I understood it is a link between the L1 norm and L2 norm of a vector. Although when they compute the upper prediction bound for LASSO I do not understand. In the noisless case they go from $$ \parallel X\hat{\beta}-X\beta^0 \parallel^2_n + 2 \lambda \parallel \hat{\beta_{S_0^c}} \parallel_1 \leq 2\lambda \parallel \hat{\beta_{S_0}}-\beta^0 \parallel_1 $$

to $$ \text{left hand side} \leq \frac{2\lambda \parallel X\hat{\beta}-X\beta^0 \parallel_n}{\phi(S;L)} $$

Using the definition: $$ \phi(S;L)= min ( \parallel X\hat{\beta}-X\beta^0 \parallel_n : \parallel\beta_S\parallel=1 ; \parallel\beta_{S_c}\parallel \leq L) $$

With S the active set, Sc its complementary set, S0 the true active set .

It sounds obvious to them that by definition those two lines follow naturally, but it is not obvious to me. Does anyone has an intuition or explaination to provide me ? Sorry if I sound a bit unclear as it is not my domain and I feel a bit lost. Don't hesistate to ask me to be clearer :)

Thanks for reading and good evening (which makes no real meaning if not on Greenwich meridian) !

  • $\begingroup$ On what page of the book are these inequalities established? $\endgroup$
    – Cm7F7Bb
    Nov 24, 2016 at 14:35

1 Answer 1


In the noiseless case, we have $$\|X\hat{\beta}-X\beta^0\|_n^2+2\lambda\|\hat{\beta}\|_1\leq2\lambda\|\beta^0\|_1 $$ $$\Rightarrow\|X\hat{\beta}-X\beta^0\|_n^2+2\lambda\|{\hat{\beta}}_{\!S_0^c}\|_1\leq2\lambda\|\beta^0\|_1-2\lambda\|{\hat{\beta}}_{\!S_0}\|_1\leq2\lambda\|\beta^0-{\hat{\beta}}_{\!S_0}\|_1.\quad(\ast)$$ It can be directly obtained from $(\ast)$ that

(1) $\ \|X\hat{\beta}-X\beta^0\|_n^2+2\lambda\|{\hat{\beta}}_{\!S_0^c}\|_1\leq2\lambda\|{\hat{\beta}}_{\!S_0}-\beta^0\|_1;\quad$ (the first conslusion)

(2) $\ \|{\hat{\beta}}_{\!S_0^c}\|_1\leq\|{\hat{\beta}}_{\!S_0}-\beta^0\|_1$.

Define $s_0=|S_0|$ as the number of indices in the true active set $S_0$. Note that there's an error in the above definition of $\phi(S,L)$, which should be corrected as $$\phi(S,L)=\min_\beta\{\sqrt{s_0}\|X\beta_S-X\beta_{S^c}\|_n:\|\beta_S\|_1=1,\|\beta_{S^c}\|_1\leq L\}.$$ Now we make an explanation for the second conclusion. It's easy to obtain from (2) that $$\|{\hat{\beta}}_{\!S_0^c}-\beta^0_{\!S_0^c}\|_1\leq\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1$$ $$\qquad\Rightarrow \left\|-\,\frac{{\hat{\beta}}_{\!S_0^c}-\beta^0_{\!S_0^c}}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1}\right\|_1=\frac{\|{\hat{\beta}}_{\!S_0^c}-\beta^0_{\!S_0^c}\|_1}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1}\leq1.$$ Let $$\delta_S=\frac{{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1},\quad \delta_{S^c}=-\,\frac{{\hat{\beta}}_{\!S_0^c}-\beta^0_{\!S_0^c}}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1}.$$ Then $$\|\delta_S\|_1=1,\quad\|\delta_{S^c}\|_1\leq1.$$ According to the definition of $\phi(S_0,1)$, we have $$\sqrt{s_0}\|X\delta_S-X\delta_{S^c}\|_n\geq\phi(S_0,1)$$ $$\Rightarrow \sqrt{s_0}\left\|\frac{X({\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0})-X({\hat{\beta}}_{\!S_0^c}+\beta^0_{\!S_0^c})}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1}\right\|_n=\sqrt{s_0}\frac{\|X{\hat{\beta}}-X\beta^0\|_n}{\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1}\geq\phi(S_0,1)$$ $$\Rightarrow \|{\hat{\beta}}_{\!S_0}-\beta^0\|_1=\|{\hat{\beta}}_{\!S_0}-\beta^0_{\!S_0}\|_1\leq\frac{\sqrt{s_0}\|X{\hat{\beta}}-X\beta^0\|_n}{\phi(S_0,1)}.\ (\text{the second conclusion})$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.