\LARGE{%Precise Error Bounds for the Constrained LAD Estimator %Asymptotically Exact Analysis the LASSO Error
%%This work was supported in part by the National Science Foundation under grants CCF-0729203
CNS-0932428 and CIF-1018927
by the Office of Naval Research under the MURI grant N00014-08-1-0747
and by a grant from Qualcomm Inc. %% %
A classical problem that arises in numerous signal processing applications %Consider the classical problem of asks for the reconstruction of an unknown, $k$-sparse signal $\x_0\in \R^n$ from underdetermined, noisy, linear measurements $\y=\A\x_0+\z\in \R^m$. One standard approach is to solve the following convex program $\hat\x=\arg\min_\x \|\y-\A\x\|_2 + \la \|\x\|_1$, which is known as the $\ell_2$-LASSO. We assume that the entries of the sensing matrix $\A$ and of the noise vector $\z$ are i.i.d Gaussian with variances $1/m$ and $\sigma^2$. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we precisely characterize the limiting behavior of the normalized squared error $\|\hat\x-\x_0\|^2_2/\sigma^2$. Our numerical illustrations validate our theoretical predictions. %A classical problem that arises in numerous signal processing applications %asks for the reconstruction of an unknown, $k$-sparse signal $x_0\in R^n$ from underdetermined, noisy, linear measurements $y=Ax_0+z\in R^m$. One standard approach is to solve the following convex program $\hat x=\arg\min_x \|y-Ax\|_2 + \lambda \|x\|_1$, which is widely known as the LASSO. We assume that the entries of the sensing matrix $A$ and of the noise vector $z$ are i.i.d Gaussian with variance $1/m$ and $\sigma^2$. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we precisely characterize the limiting behavior of the noise sensitivity $\|\hat x-x_0\|^2_2/\sigma^2$. Our numerical illustrations validate our theoretical predictions. %The asymptotic analysis of the LASSO has been recently advanced utilizing a celebrated theorem of Gordon. It has been shown that the asymptotic behavior of the LASSO by a sensing matrix with independent identically distributed Gaussian entries is completely determined by a simpler optimization. In this paper, we show that the latter can also be replaced by a deterministic two-dimensional optimization, which is simple to evaluate by numerical means. We particularly provide the exact error magnitude for an arbitrary signal to noise ratio. We also connect the previous results to the proposed deterministic optimization by analysis and provide some further implications.
analysis.tex
\vspace{-18pt}
\section{Analysis}

\vspace{-10pt}
\subsection{Problem Setup}\label{sec:setup}
\vspace{-5pt}
For the rest of the paper, let $\Nn(\mu,\sigma^2)$ denote the normal distribution of mean $\mu$ and variance $\sigma^2$. Also, we use $\|\cdot\|$ instead of $\|\cdot\|_2$. Let $\x_0\in\R^n$ denote the unknown signal and $\y=\A\x_0 + \z\in\R^m$ denote the vector of observations. We make the following assumptions:
\vspace{-6pt}
\begin{itemize}
\item the entries of $\A$ are i.i.d $\Nn(0,1/m)$,
\vp
\item the entries of $\z$ are i.i.d $\Nn(0,\sigma^2)$,
\vp
\item $\x_0$ is $k$-sparse with \emph{fixed} support set $S$, i.e. $(\x_0)_i=0$ for all $i\notin S$. Also, $(\x_0)_i\overset{\text{i.i.d}}{\sim}\Nn(0,1)$,
%\item $n,m,k\rightarrow\infty$ with $m/n\rightarrow\delta \in(0,1)$ \footnote{Our analysis extends to the overdetermined case, where $\delta\in[1,\infty)$. For simplicity, in this paper we focus on the more interesting regime of underdetermined measurements. } and $k/m\rightarrow \gamma\in(0,1)$.
\end{itemize}
\vspace{-8pt}
Consider estimating $\x_0$ via the solution $\hat\x:=\hat\x(\la)$ of the LASSO program in \eqref{eq:LASSO}.
%\begin{align}\label{eq:opt}
%\min_{\x} \Lc(\x;\A,\y) := \|\y-\A\x\| + \frac{\la}{\sqrt{m}} \|\x\|_1.
%\end{align}
Our goal is to provide tight expressions for the reconstruction error $\|\hat\x-\x_0\|$;
% and for the optimal cost $\Lc(\hat\x)$
%  of the LASSO in \eqref{eq:LASSO}. 
%The quantity of interest $\|\hat\x-\x_0\|$
% and $\Lc(\hat\x)$ 
this depends explicitly on $\x_0$ and implicitly on $\A$ and $\z$.
%, thus our result is probabilistic in nature. 
We consider an asymptotic setting in which the problem parameters $n,m$ and $k$ grow proportionally as $m/n\rightarrow\delta \in(0,1)$ \footnote{Our analysis extends to the overdetermined case, where $\delta\in[1,\infty)$. For simplicity, in this paper we focus on the  underdetermined regime. } and $k/m\rightarrow \gamma\in(0,1)$. Our result characterizes the limiting behavior of the quantity of interest as $n\rightarrow\infty$. To suppress notation, we use the symbol ``$\approx$" to denote convergence in probability, i.e. $X_n\approx X$ is used to denote that a sequence of random variables $X_n$ converges in $X$ in that for all $\eps>0$, $\lim_{n\rightarrow\infty}\Pro\left( |X_n - X|>\eps X \right) = 0$. Similarly, we write $X_n\gtrsim X$ if for all $\eps>0$, $\lim_{n\rightarrow\infty}\Pro\left( X_n < (1-\eps) X \right) = 0$.

\vspace{-12pt}
\subsection{Preliminaries}

\vp
%For the purpose of the analysis, 
It is convenient to rewrite \eqref{eq:LASSO} changing the optimization variable to the error vector $\w:=\x-\x_0$:
\footnote{Also, note the re-scaling in \eqref{eq:main} with a factor of $\sqrt{m}$. 
}:
\begin{align}\label{eq:main}
\min_{\w} \Lc(\w;\A,\z) := \sqrt{m}\|\z-\A\w\| + \la \|\x_0 + \w\|_1.
\end{align}
Denote $\hat\w^{\la,\sigma}(\A,\z)$ the solution of \eqref{eq:main}. We often drop the dependence on the arguments $\la,\sigma,\A,\z$ when clear from context.
Suppose we want to show that $\|\hat\w\|\approx \alphas$, for  appropriate $\alpha_*\geq 0$. Equivalently, for all $\eps>0$ and sets $\Rc_\eps:=\{\ell~|~ |\ell -\alphas| > \eps\alphas\}$, we wish that $\lim_{n\rightarrow\infty}\Pro( \|\hat\w\|\in\Rc_\eps ) = 0$. It suffices to prove the existence of $\delta:=\delta(\eps)>0$ such that  
\vspace{-10pt}
\begin{align}\label{eq:prob_state}
\lim_{n\rightarrow \infty}\Pro\left( \min_{\|\w\|\in \Rc_\eps} \Lc(\w) \leq (1+\delta ) \Lc(\hat\w) \right) = 0.
\end{align}
%The first step towards proving \eqref{eq:prob_state}, is to 
%\vspace{-3pt}
Directly showing \eqref{eq:prob_state} through analyzing $\Lc(\w)$ is difficult. Instead, we use the Gaussian min-max Theorem to translate the LASSO objective function in \eqref{eq:main} to a simpler one, that is amenable to direct analysis.

\vspace{-10pt}
\subsection{Introducing a Simpler Optimization}
\vp
The Gaussian min-max Theorem belongs to the family of the so called Gaussian comparison inequalities \cite[Ch.~3]{Ledoux} and was proved by Gordon in \cite[Lemma 3.1]{Gor}. To see how that theorem can be applied in our case, observe that
\vspace{-8pt}
$$
\Lc(\w) = \max_{\|\ub\|\le 1} \ub^T[\sqrt{m}\A, -\z/{\sigma}]\left [
\begin{array}{c}
\w \\
\sqrt{m}\sigma \\
\end{array}
\right ]+\lambda\|\x_0+\w\|_1.
$$
Let $\g\in\R^m$, $\h\in\R^n$, $g\in\R$ have i.i.d $\Nn(0,1)$ entries and
\vp
\begin{align}
&\Gc(\w;\g,\h) := \max_{\|\ub\|\le 1}\Big\{ \sqrt{\|\w\|^2+m\sigma^2}\g^T\ub \nn\\
&\qquad\qquad-\|\y\|(\h^T\w+\sqrt{m}\sigma g)+\lambda\|\w+\x_0\|_1 \Big\}.\label{eq:Gw}
\end{align}
Then, the Gaussian min-max Theorem\footnote{In fact, the statement in \eqref{eq:low} is a slight variation of the original statement of the Gaussian min-max Theorem. Please refer to \cite{tight} for details.} states that for arbitrary set $\Rc\subset\R^n$ and $c\in\R$:
\begin{align}\label{eq:low}
\Pro( \min_{\w\in\Rc} \Lc(\w;\A,\z) \leq c)\leq 2\Pro( \min_{\w\in\Rc} \Gc(\w;\g,\h) \leq c ).
\end{align}
 Recently, it was shown in \cite{StoLASSO,tight} that when combined with appropriate convexity assumptions, the Gaussian min-max Theorem is \emph{tight}. In particular, for a \emph{convex} compact set $\Rc$ it is also true \cite[Theorem II.1]{tight} that 
\vp
\begin{align}\label{eq:up}
\Pro( \min_{\w\in\Rc} \Lc(\w;\A,\z) \geq c)\leq 2\Pro( \min_{\w\in\Rc} \Gc(\w;\g,\h) \geq c ).
\end{align}
\eqref{eq:low} and \eqref{eq:up} are critical for establishing \eqref{eq:prob_state}. They suggest the analysis of the following optimization problem\footnote{ The proof of \eqref{eq:up} in \cite{tight} requires the set $\Rc$ to be compact. This technical detail can be resolved by assuming a sufficiently large upper bound $K$ on $\|\hat\w\|$ such that constraining the minimization in \eqref{eq:2ana} over the set $\|\w\|\leq K$ does not change the optimal cost.}, which we refer to as ``Gordon's optimization (GO)":
\vp
\begin{align}\label{eq:2ana}
(GO)\quad\quad\Gc(\ws;\g,\h):= \min_{\w}\Gc(\w;\g,\h),
\end{align}
in place of the original LASSO optimization in \eqref{eq:main}. To see how this can be useful, assume that $\Gc(\ws)\approx \Dc_*$; then, it would follow directly from \eqref{eq:low} and \eqref{eq:up} that $\Lc(\hat\w)\approx \Dc_*$. Next, we analyze such asymptotic properties of (GO) .

%
\begin{figure*}[!t]
% ensure that we have normalsize text
%\normalsize
\footnotesize
%
%\startcounter{15}
\begin{align}\label{eq:defn}
%&\rho(c,\la) := \E_{g\sim\Nn(0,1)}\left[\shrink^2(c g,\la)\right] = 2(c^2+\la^2)Q(\la/c) - \sqrt{2/\pi} c\la e^{-{\la^2}/{(2c^2)}}, 
%\quad Q(x) = (1/\sqrt{2\pi})\int_{x}^{\infty}e^{-x^2/2}\mathrm{d}x,\nn
%\\%\label{eq:rho}\\
&\Dlf := k(1+\la^2) + (n-k)\rho(1,\la),\quad
\Clf := -(\la/2) \partial\Dlf/\partial\la, \quad\psi(\la) := \la/Q^{-1}\left( {1}/{2} + ({m-\Dlf-\Clf})/({2k}) \right),\nn\\
&f(\la,\phi) := m- \Dlf + m{\sigma^2}(1-\phi^2) + k\left(\phi^2 - \la^2- 2\right)\left(2Q\left({\la}/{\phi}\right)-1\right) +  k \sqrt{{2}/{\pi}}{\lambda\phi}\exp\left(-{\la^2}/({2\phi^2})\right). &
\end{align}
\hrulefill
\vspace*{4pt}
\end{figure*}
%



\vspace{-8pt}
\subsection{Analyzing Gordon's Optimization}
\vspace{-5pt}
\subsubsection{Scalarization}
\vspace{-5pt}
We begin with simplifying (GO) and reducing it to an optimization problem involving only scalars. For now, assume that $\g,\h$ and $g$ are all fixed. 
Note that the maximization over the direction of $\ub$ in \eqref{eq:Gw} is easy to evaluate. Furthermore, we may write $\|\x_0+\w\|_1 = \max_{\|\vb\|_\infty\leq 1}(\x_0+\w)^T\vb$. With these:\vp
%\begin{align}\label{eq:Gw2}
%\Gc(\w;\g,\h) &= \max_{\substack{0\leq\beta\leq 1\\ \|\vb\|_\infty\leq 1}}\Big\{ \sqrt{\|\w\|^2+m\sigma^2}\|\g\|\beta \\ \vp
%&\quad\quad-\beta(\h-\la\vb)^T\w+\beta\sqrt{m}\sigma g+\lambda\x_0^T\vb\Big\}.\nn
%\end{align}
\begin{align}\label{eq:Gw2}
\Gc(\w_*) &= \min_{\w}\max_{\substack{0\leq\beta\leq 1\\ \|\vb\|_\infty\leq 1}}\Big\{ \sqrt{\|\w\|^2+m\sigma^2}\|\g\|\beta \\ \vp
&\quad\quad-\beta(\h-\la\vb)^T\w-\beta\sqrt{m}\sigma g+\lambda\x_0^T\vb\Big\}.\nn
\end{align}
%To suppress notation denote the objective function in \eqref{eq:Gw2} as $\Gco(\w,\beta,\vb)$. Then, 
%\begin{align}\label{eq:minmax}
%\Gc(\ws) = \min_{\w}\max_{\substack{0\leq\beta\leq 1\\ \|\vb\|_\infty\leq 1}}\Gco(\w,\beta,\vb).
%\end{align}
\vspace{-2pt}
The objective function in \eqref{eq:Gw2} is convex-concave in $\w$ and $\beta,\vb$. Also, the constraint sets are closed convex and one of them is bounded; thus, we can switch the correspoding order of min-max \cite[Cor.~
37.3.2]{Roc70}. After this, the minimization over the direction of $\w$ is easy to evaluate:
\vspace{-8pt}
\begin{align}
\Gc(\ws) &= \max_{\substack{0\leq\beta\leq 1\\ \|\vb\|_\infty\leq 1}}\min_{\alpha\geq 0} \Big\{ \sqrt{\alpha^2+m\sigma^2}\|\g\|_2\beta\nn-\beta\sqrt{m}g\sigma
\\ 
&\qquad\qquad\qquad-\alpha\|\lambda \vb-\beta\h\|_2+\lambda \x_0^T\vb\Big\}.\nn
\end{align}
Note that the optimization variable $\alpha$ above plays the role of the $\ell_2$-norm of $\w$; its optimal value $\alphas$ is equal to $\|\w_*\|_2$. Switching one last time the order of optimization between $\vb,\beta$ and $\alpha$, we conclude with the following optimization:
\begin{align*}
\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1}}\left\{ \sqrt{\alpha^2+m\sigma^2}\|\g\|_2\beta-\beta\sqrt{m}g\sigma-\beta\Fc(\alpha,\beta)\right\},
\end{align*}
where $\Fc(\alpha,\beta) := \min_{\|\vb\|_\infty\le 1}\left\{\alpha\|\frac{\lambda}{\beta} \vb-\h\|_2-\frac{\lambda}{\beta} \x_0^T\vb\right\}.$ The final step amounts to reducing the optimization over $\vb$ to a scalar optimization. The idea here is to apply the fact that for any real $r\ge 0$, one has $\sqrt{r}=\min_{p>0}\left(\frac{p}{2}+\frac{r}{2p}\right)$ in order to make the objective function separable. With this:
\vp
\begin{align}
&\mathcal{F}(\alpha,\beta)=\min_{\|\vb\|_\infty\le 1}\min_{p>0}\frac{\alpha p}{2}+\frac{a\|\lambda/\beta \vb-\h\|_2^2}{2p}-\frac{\lambda}{\beta} \x_0^T\vb\nn\\
%&=\min_{p>0}\bigg \{\frac{\alpha p}{2}+\sum_{i\in S}\min_{|\vb_i|\le \lambda/\beta}\left[\frac{\alpha}{2p}\left(\vb_i-\h_i\right)^2-\frac{1}{\sigma}(\x_0)_{i}\vb_i\right]\nonumber+\sum_{i\in S^c}\min_{|\vb_i|\le \lambda/\beta}\frac{\alpha}{2p}\left(\vb_i-\h_i\right)^2\bigg \} \\
&=\min_{p>0}\bigg \{\frac{\alpha p}{2}+\sum_{i\in S}\Big[\frac{\alpha}{2p}\min_{|\vb_i|\le \frac{\lambda}{\beta}}\left(\vb_i-\h_i-\frac{p(\x_0)_i}{\alpha}\right)^2\nn
\\
&-\frac{p(\x_0)_i^2}{2\alpha}-\h_i(\x_0)_i\Big]+\frac{\alpha}{2p}\sum_{i\notin S}\min_{|\vb_i|\le \frac{\lambda}{\beta}}\left(\vb_i-\h_i\right)^2 \bigg \}.\label{eq:above}
\end{align}
The second equality above follows from standard completion of squares. The scalar minimizations over $\vb_i$'s in \eqref{eq:above} are simple soft-thresholding operations: $\min_{|q|\leq\tau}(r-q)^2 = 
%\shrink(r,\tau):=
( (|r|-\tau)^+ )^2.$
%\begin{align}
%\min_{|q|\leq\tau}(r-q)^2 = 
%%Now, for any real $r$ and $\tau\ge0$, denote the shrinkage operator as
%%\begin{equation*}
%\shrink(r,\tau):= (|r|-\tau)^+.
%%\begin{cases}
%%|r|-\tau&|r|>\tau,\\
%%0&|r|\le\tau.
%%\end{cases}
%\end{align}
Combining all the above, we have shown that
%\vspace{-5pt}
$
%\begin{align}
\Gc(\ws) = \min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1, p>0}} \Gco(\alpha,\beta,p),
%\end{align}
$
%\vspace{0pt}
for an appropriately defined objective function $\Gco(\alpha,\beta,p)$.
%where
%\begin{align}
%\Gc(\alpha,\beta,p)&=&\min_{p>0}\bigg \{\frac{\alpha p}{2}+\sum_{i\in S}\left[\frac{\alpha}{2p}\shrink^2(\h_i+\frac{p(\x_0)_i}{\alpha\sigma},\lambda/\beta)-\frac{p(\x_0)_i^2}{2\alpha\sigma^2}-\frac{1}{\sigma}\h_i(\x_0)_i\right]\nonumber+\sum_{i\in S_0}\frac{\alpha}{2p}\shrink^2(\h_i,\lambda/\beta) \bigg \}
%\end{align}

\vspace{-10pt}
\subsubsection{Concentration}
\vp
Our next step is to analyze the limiting behavior of $\Gco(\alpha,\beta,p)$. Recall that $\g,\h,g$  have i.i.d $\Nn(0,1)$ entries. Thus, $\|\g\|\approx\sqrt{m}$ and $g\approx 0$. Using these and applying the Law of Large Numbers to the summations in \eqref{eq:above} it can be shown that
$\Gco(\alpha,\beta,p)\approx \Dc(\alpha,\beta,p),
$ where 
\begin{align}\nn
&\Dc(\alpha,\beta,p):=\beta\Big( \sqrt{\alpha^2+m\sigma^2}\sqrt{m} - \frac{\alpha p}{2} +  k\frac{p}{2\alpha} \nn\\
& - k\frac{\alpha}{2p} \rho(\sqrt{1+p^2/\alpha^2} , \la/\beta  ) -(n-k) \frac{\alpha}{2p} \rho( 1 , \la/\beta  ) \Big),\nn
\end{align}
\vspace{-10pt}
\begin{align}\label{eq:D}
\rho(c,\tau)& := \E_{g\sim\Nn(0,1)}\left[ (|cg|-\tau)^+\right]^2\nn\\
 &= 2(c^2+\tau^2)Q(\tau/c) - \sqrt{2/\pi} c\tau e^{-{\tau^2}/{(2c^2)}},%\label{eq:rho}
\end{align}
and $Q(x) = (1/\sqrt{2\pi})\int_{x}^{\infty}e^{-x^2/2}\mathrm{d}x$.
%and $\rho(\cdot,\cdot)$ is defined in \eqref{eq:defn}. 
Albeit some technicalities involved (skipped due to space limitations):
%we have shown that
\vspace{-8pt}
\begin{subequations}
\begin{align}
\min_{\w} \Gc(\w)&\approx\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p),\label{eq:f1}\\
\min_{\|\w\| \in \Rc_\eps} \Gc(\w)&\approx\min_{\alpha\in\Rc_\eps}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p)\label{eq:f2}.
\end{align}
\end{subequations}
\vp
with $\Rc_\eps = \{\ell ~|~ |\ell -\alpha_*|>\eps\alpha_* \}$ and $\alphas$ minimizer in \eqref{eq:f1}.


\vspace{-10pt}
\subsection{Back from Gordon's Optimization to the LASSO}
\vp
Once we have analyzed (GO), we may now appropriately apply the Gaussian min-max Theorem (in particular, \cite[Thm. II.1]{tight}) to conclude with the following result.
\vspace{-3pt}
\begin{thm}[LASSO Objective]\label{thm:obj0}
 Recall the definitions of $\Lc(\w)$, $\Dc(\alpha,\beta,p)$ in \eqref{eq:main} and \eqref{eq:D}, respectively. Also, let
$\Lc_*:= \min_\w \Lc(\w)$ and $ \Dc_*:=\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p).$
%\vspace{-8pt}
Then, for all $\eps>0$,
%\begin{align}\label{eq:!1}
$\lim_{n\rightarrow\infty}\Pro( |\Lc_*-\Dc_*|>\eps\Dc_* ) = 0.$
%\end{align}
% the following limits hold in probability
%\begin{align}
%\Lc_*:= \min_\w \Lc(\w)&\approx\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p)=: \Dc_*\label{eq:!1}
%\end{align}
%% COMMENT******** INSEAD write: the following limit holds in probability \lim_{n\rightarrow\infty} \frac{\Lc_*}{n} = ...
%\begin{subequations}
%\begin{align}
%\min_\w \Lc(\w)&\approx\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p),\label{eq:!1}\\
%\min_{\|\w\| \in \Rc_\eps} \Lc(\w) &\gtrsim \min_{\alpha\in\Rc_\eps}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p).\label{eq:!2}
%\end{align}
%\end{subequations}
%\begin{subequations}
%\begin{align}
%\Lc_*:= \min_\w \Lc(\w)&\approx\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p)=: \Dc_*\label{eq:!1}\\
%\hspace{-5pt}\Lc_\eps: =\min_{\|\w\| \in \Rc_\eps} \Lc(\w) &\gtrsim \min_{\alpha\in\Rc_\eps}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p) =:\Dc_\eps\label{eq:!2}
%\end{align}
%\end{subequations}
%\eqref{eq:!1}
\end{thm}
%\vp
%$$
%\Lc_\eps: =\min_{\|\w\| \in \Rc_\eps} \Lc(\w),~~ \Dc_\eps:=\min_{\alpha\in\Rc_\eps}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p).
%$$
%In the theorem above, \eqref{eq:!2} is a result of \eqref{eq:f2} when applying \eqref{eq:low}; 
\vspace{-6pt}
\noindent The proof follows from \eqref{eq:f1} when combining \eqref{eq:low} and \eqref{eq:up}. 
Also, a single application of \eqref{eq:low} in \eqref{eq:f2} shows that for any  $\R_\eps\subset\R$:
%\vp
\begin{align}
\hspace{-5pt}\Lc_\eps: =\min_{\|\w\| \in \Rc_\eps} \Lc(\w) &\gtrsim \min_{\alpha\in\Rc_\eps}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p) =:\Dc_\eps\label{eq:!2}.
\end{align}

To appreciate the power of Theorem \ref{thm:obj0}, note that it gives an explicit evaluation of the limiting behavior of the LASSO  optimal cost in terms of the optimal cost of a much simpler, scalar and deterministic optimization problem.
%, as it appears on the right-hand side of  \eqref{eq:!1}. 
%(see the first statement of Theorem \ref{thm:main} below). 
%What is more, the relation between the LASSO and this simpler optimization problem goes beyond that; it turns out that the LASSO reconstruction error $\|\hat\w\|_2$ converges to the optimal solution $\alpha_*$ of the scalar and deterministic optimization problem. 
What is more, we can combine Theorem \ref{thm:obj0} with \eqref{eq:!2}, to prove the following result about the limiting behavior of the LASSO error.
% \eqref{eq:prob_state}, which in turn implies that the LASSO reconstruction error $\|\hat\w\|_2$ converges to the optimal solution $\alpha_*$ of the scalar and deterministic optimization problem.
%\vspace{-7pt}
\begin{thm}[LASSO error]\label{thm:err0}
Let $\hat\x$ be a minimizer of the LASSO in \eqref{eq:LASSO} and recall the definition of function $\Dc(\alpha,\beta,p)$ \eqref{eq:D}. If $\alpha_*$ is optimal for $\min_{\alpha\geq 0}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p)$, then for all $\eps>0$:
$\lim_{n\rightarrow\infty}\Pro( |\|\hat\x-\x_0\|_2 - \alpha_*|>\eps\alpha_* ) = 0.
$
\end{thm}
\vspace{-5pt}
 We provide a sketch of the proof here (see also \cite[Thm.~II.1]{tight}).
%; see \cite{inPrep} for details. 
Consider the event

$
\Ec= \left\{  \Lc_*\leq (1+\zeta_1)\Dc_* \text{ and } \Lc_\eps\geq (1-\zeta_2)\Dc_\eps \right\}
$.

\noindent In view of Thm.~\ref{thm:obj0} and \eqref{eq:!2}:
%  for all $\zeta_1,\zeta_2$ that
   $\lim_{n\rightarrow\infty}\Pro(\Ec) = 1$. Hence,
\vspace{-10pt}
\begin{align}
&\lim_{n\rightarrow\infty}\Pro\left( \Lc_\eps \leq (1+\delta ) \Lc_* \right) \leq\lim_{n\rightarrow\infty} \Pro\left( \Lc_\eps \leq (1+\delta ) \Lc_*  |\Ec\right)\nn\\
&\quad\quad\leq \Pro\left( ~(1-\zeta_2)\Dc_\eps \leq (1+\delta)(1+\zeta_1) \Dc_*~ \right).\label{eq:ab44}
\end{align}
%\vspace{-3pt}
Next, we show that we can choose $\zeta_1,\zeta_2,\delta$ such that the (deterministic) event in \eqref{eq:ab44} does not occur; this will complete the proof of \eqref{eq:prob_state}.
It can be shown %(see \cite{inPrep} for details)
 that the function $\Dc(\cdot,\beta,p)$ is strictly convex for all $\beta,p$. Thus, $\exists$ constant $L>0$ :
 \vspace{-10pt}
\begin{align}
&\Dc_\eps - \Dc_* =: \Dc(\alpha_\eps,\beta_\eps,p_\eps) - \Dc(\alphas,\betas,p_*) = \nn\\
&{\Dc(\alpha_\eps,\beta_\eps,p_\eps) - \Dc(\alpha_\eps,\beta_*,p_*)} + {\Dc(\alpha_\eps,\beta_*,p_*)- \Dc(\alphas,\betas,p_*)}\nn\\
&\vspace{-5pt}\geq 0 + L|\alpha_\eps - \alpha_*|^2 \geq \eps^2 L \alpha_*^2.\label{eq:str}
\end{align}
%\begin{align}
%&\Dc_\eps - \Dc_* =: \Dc(\alpha_\eps,\beta_\eps,p_\eps) - \Dc(\alphas,\betas,p_*) = \nn\\
%&\underbrace{\Dc(\alpha_\eps,\beta_\eps,p_\eps) - \Dc(\alpha_\eps,\beta_*,p_*)}_{\geq 0} + \underbrace{\Dc(\alpha_\eps,\beta_*,p_*)- \Dc(\alphas,\betas,p_*)}_{\geq L|\alpha_\eps - \alpha_*|^2}\nn\\
%&\vspace{-5pt}\geq \eps^2 L \alpha_*^2.\label{eq:str}
%\end{align}
\vspace{-2pt}
Denote $\theta=\theta(\eps):=\eps^2 L \alpha_*^2/\Dc_*$. Set $\zeta_1=\theta/4$, $\zeta_2=\frac{\theta/2}{1+\theta}$, $\delta=\frac{\theta}{4+\theta}$ and apply \eqref{eq:str} to complete the proof.
%\lim_{n\rightarrow \infty}

\vspace{-10pt}
\subsection{Simplifying the Result}
\vspace{-7pt}
For any values of $\la$ and $\sigma$, we ask for an accurate prediction of the LASSO error $\|\hat\x^{\la,\sigma}-\x_0\|$. 
Theorem \ref{thm:err0} yields an answer
%  accurate prediction of the LASSO error $\|\hat\w^{\la,\sigma}\|$ 
as the solution of a minimax optimization, which is scalar, deterministic and convex.
%. Although, the optimization problem is scalar, deterministic and convex, the brute-force way of numerically solving it via exhaustive search over the involved parameters can be computationally rpohibitive.
We have put some additional effort in order to simplify this optimization and make it more explicit. In particular, we can show that it has a unique global optimal solution, the evaluation of which essentially breaks down to solving two nonlinear one-dimensional algebraic equations (see Theorem \ref{thm:main}). Apart from the computational advantage of this alternative description, it also allows for further theoretical insights. For instance, starting from Theorem \ref{thm:main} we believe that it is possible to prove that the worst-case NSE is attained in the limit of the noise variance $\sigma^2\rightarrow 0$.% (see Theorem \ref
% We have performed further careful analysis of the structural properties of the optima of this minimax optimization and have shown that it has a unique global optimal solution, the evaluation of which essentially breaks down to solving two nonlinear one-dimensional algebraic equations (see Theorem \ref{thm:main}). Apart from the computational advantage of this alternative description, it also allows for further theoretical insights. For instance, starting from Theorem \ref{thm:main} we believe that it is possible to prove that the worst-case NSE is attained in the limit of the noise variance $\sigma\rightarrow 0$.% (see Theorem \ref{thm:WNS})

%\begin{align}
%\lim_{n\rightarrow\infty}\Pro \left(\min_{\|\w\| \in \Rc_\delta} \Lc(\w) \leq (1-\eps) \min_{\alpha\in\Rc_\delta}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p) \right) = 0,
%\end{align}
%\begin{align}
%\min_{\|\w\| \in \Rc_\delta} \Lc(\w) \gtrsim \min_{\alpha\in\Rc_\delta}\max_{\substack{0\leq\beta\leq 1\\ p>0}}\Dc(\alpha,\beta,p) ,
%\end{align}


commands.tex
%Equations
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{align}}
\newcommand{\eea}{{\end{align}}}

\DeclareMathOperator{\shrink}{\eta}
\newcommand{\Lh}{\hat{\mathcal{L}}}
\newcommand{\lah}{\hat{\la}}
\newcommand{\Dlfh}{{\mathbf{D}}(\lah )}
\newcommand{\Db}{{\mathbf{D}}}
\newcommand{\Cb}{{\mathbf{C}}}

\newcommand{\Qlabd}{Q\left(\frac{\la}{\delta\beta}\right)}
\newcommand{\Qlad}{Q\left(\frac{\la}{\delta}\right)}
\newcommand{\Qlab}{Q\left(\frac{\la}{\beta}\right)}

\newcommand{\elabd}{e^{-\frac{\la^2}{2\delta^2\beta^2}}}
\newcommand{\elad}{e^{-\frac{\la^2}{2\delta^2}}}
\newcommand{\elab}{e^{-\frac{\la^2}{2\beta^2}}}

\newcommand{\Dlfb}{{\mathbf{D}}\left(\frac{\la}{\beta} \right)}
\newcommand{\Clfb}{{\mathbf{C}}\left(\frac{\la}{\beta} \right)}

\newcommand{\Qinv}{Q^{-1}}

\newcommand{\alphas}{\alpha_*}
\newcommand{\ps}{p_*}
\newcommand{\betas}{\beta_*}

\newcommand{\Ec}{\mathcal{E}}
\newcommand{\Rc}{\mathcal{R}}
\newcommand{\Gco}{\mathcal{\Gc}_o}
\newcommand{\wo}{\overline{\w}}
\newcommand{\ws}{{\w}_*}

%\newcommand{\=}{\approx}

\newcommand{\rP}{\xrightarrow{P}}

\newcommand{\vp}{\vspace{-5pt}}
%Bold upper
\newcommand{\M}{\mathbf{M}}
\newcommand{\tC}{\tilde{\mathbf{C}}}
\newcommand{\tD}{\tilde{\mathbf{D}}}
\newcommand{\Fh}{\mathbf{\hat{F}}}
\newcommand{\ft}{\mathbf{\tilde{f}}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\W}{\mathbf{W}}
\newcommand{\U}{\mathbf{U}}
\newcommand{\V}{\mathbf{V}}
\newcommand{\F}{\mathbf{F}}
\newcommand{\Delxf}{{\mathbf{D}}_f(\x_0,{\mathbf{R}}^+)}
\newcommand{\Pelxf}{{\mathbf{P}}_f(\x_0,{\mathbf{R}}^+)}
\newcommand{\Celxf}{{\mathbf{C}}_f(\x_0,{\mathbf{R}}^+)}
\newcommand{\Dlf}{{\mathbf{D}}(\la )}
\newcommand{\Dlfc}{{\mathbf{D}}(\lac )}
\newcommand{\order}[1]{\mathcal{O}\left(#1\right)}

\newcommand{\Dmin}{{\mathbf{D}}^*_f}
\newcommand{\Plf}{{\mathbf{P}}_f(\x_0,\la )}
\newcommand{\Df}{{\mathbf{D}}_f(\x_0,}
\newcommand{\Pf}{{\mathbf{P}}_f(\x_0,}
%\newcommand{\Clf}{{\mathbf{C}}_f(\x_0,\la )}
\newcommand{\Clf}{{\mathbf{C}}(\la )}
\newcommand{\Cf}{{\mathbf{C}}_f(\x_0,}


\newcommand{\DC}{{\mathbf{D}}(\Cc)}
\newcommand{\CC}{{\mathbf{C}}(\Cc)}
\newcommand{\PC}{{\mathbf{P}}(\Cc)}


\newcommand{\lac}{\lambda_{\text{crit}}}
\newcommand{\labb}{\lambda_{\text{best}}}
\newcommand{\taub}{\tau_{\text{best}}}
\newcommand{\lam}{\lambda_{{\max}}}
%\newcommand{\cn}{\text{all}}

\newcommand{\dlf}{\delta(\la\paf)}
\newcommand{\delf}{\delta(\text{cone}(\paf))}

\newcommand{\DelxC}{{\mathbf{\Delta}}_\Cc(\x_0)}
\newcommand{\Gb}{\mathbf{G}}
\newcommand{\Sb}{\mathbf{S}}
\newcommand{\X}{\mathbf{X}}
\newcommand{\A}{\mathbf{A}}
\newcommand{\Lb}{\mathbf{L}}
\newcommand{\Y}{\mathbf{Y}}

%Bold lower
\newcommand{\bu}{\text{Proj}}
\newcommand{\corr}{\text{cor}}
\newcommand{\bi}{{\Pi}}
\newcommand{\w}{\mathbf{w}}
\newcommand{\heta}{\hat{E}}
\newcommand{\geta}{\hat{\zeta}}
\newcommand{\feta}{{E^*}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\ub}{\mathbf{u}}
\newcommand{\g}{\mathbf{g}}
\newcommand{\vb}{\mathbf{v}}
\newcommand{\q}{\mathbf{q}}
\newcommand{\p}{\mathbf{p}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\e}{\mathbf{e}}
\newcommand{\fh}{{\hat{f}}}
\newcommand{\tb}{\mathbf{t}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\s}{\mathbf{s}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\zo}{\overline{\mathbf{z}}}
\newcommand{\bseta}{{\boldsymbol{\eta}}}
\newcommand{\Iden}{\mathbf{I}}
\newcommand{\cb}{\mathbf{c}}  
\newcommand{\ab}{\mathbf{a}}
\newcommand{\oneb}{\mathbf{1}}
\newcommand{\h}{\mathbf{h}}
\newcommand{\hx}{{\mathbf{x}}^{*}(\la,\z)}
\newcommand{\fx}{\hat{\mathbf{x}}(\la,\z)}
\newcommand{\hw}{{\mathbf{w}}^{*}(\la,\z)}
\newcommand{\wh}{\hat{\mathbf{w}}}
\newcommand{\fw}{\hat{\mathbf{w}}(\la,\z)}
\newcommand{\ffw}{\hat{\mathbf{w}_r}(\la,\z)}
\newcommand{\xn}{{\mathbf{x}}_0}

%hat, tilde, etc
\newcommand{\tih}{\tilde{\mathbf{h}}}
\newcommand{\tz}{\tilde{\z}}
\newcommand{\tw}{\tilde{\w}}
\newcommand{\bT}{{\bar{T}}}
\newcommand{\bP}{{\bar{P}_\w}}
\newcommand{\wP}{{{P}_\w}}
\newcommand{\bS}{{\bar{S}}}

%Calligrophic
\newcommand{\Sc}{{\mathcal{S}}}
\newcommand{\map}{{\text{map}}}
\newcommand{\call}{{\text{calib}}}
\newcommand{\Rca}{{\mathcal{R}}}
\newcommand{\Rco}{{\mathcal{R}}_{\text{ON}}}
\newcommand{\Rcf}{{\mathcal{R}}_{\text{OFF}}}
\newcommand{\Rci}{{\mathcal{R}}_{\infty}}
\newcommand{\Rr}{\mathbf{\rho}}
%\newcommand{\Sc}{{\mathcal{S}_{\Lb_0,\Sb_0}}}
%\newcommand{\Sc}{{\pa({\Lb_0,\Sb_0})}}
\newcommand{\Bc}{{\mathcal{B}}}
\newcommand{\Yc}{\mathcal{Y}}
\newcommand{\Dc}{\mathcal{D}}
%\newcommand{\Lc}{\mathcal{L}}
\newcommand{\Lc}{\Phi}
\newcommand{\Ldev}{\mathcal{L}_{dev}}
\newcommand{\Xc}{\mathcal{X}}
\newcommand{\Zc}{\mathcal{Z}}
\newcommand{\Uc}{\mathcal{U}}

\newcommand{\Kc}{\mathcal{K}}
\newcommand{\Nc}{\text{Null}}
%\newcommand{\Rc}{\text{Range}}
\newcommand{\Nn}{\mathcal{N}}
\newcommand{\Cc}{\mathcal{C}}
%\newcommand{\Gc}{\mathcal{G}}
\newcommand{\Gc}{\phi}
\newcommand{\Ac}{\mathcal{A}}
\newcommand{\Pc}{\mathcal{P}}

%Math BB
\newcommand{\R}{\mathbb{R}}
\newcommand{\Pro}{{\mathbb{P}}}
\newcommand{\E}{{\mathbb{E}}}

%Greek, etc.
\newcommand{\xu}{\hat{x}_i}
\newcommand{\xz}{x_{0,i}}
\newcommand{\wi}{\hat{w}_i}

\newcommand{\ti}{\tilde}
\newcommand{\el}{\eta_{DN}(\la,\z)}
\newcommand{\paf}{\pa f(\x_0)}
\newcommand{\pef}{\pa f(\x)}
\newcommand{\dir}{D_{f,\x}(\w)}
\newcommand{\din}{D_{f,\x_0}(\w)}
\newcommand{\paw}{\pa f'_{\x_0}(\w)}
\newcommand{\fp}{f'_{\x_0}}
\newcommand{\ff}{\hat{f}_{\x_0}}
\newcommand{\ffx}{\hat{f}_{\x}}
\newcommand{\ffr}{f_{r,\x_0}}
\newcommand{\ffrx}{f_{r,\x}}
\newcommand{\la}{{\lambda}}
\newcommand{\lab}{{\bm{\lambda}}}
\newcommand{\eps}{\epsilon}
\newcommand{\om}{\omega}
\newcommand{\si}{\sigma}
\newcommand{\st}{\star}
\newcommand{\Fc}{\mathcal{F}}
\newcommand{\Tc}{\mathcal{T}}
\newcommand{\pa}{\partial}

\newcommand{\mub}{\boldsymbol{\mu}}
%Rest
\newcommand{\sg}{\text{sgn}}
\newcommand{\hg}{\hat{g}}
\newcommand{\Du}{\text{dual}}
\newcommand{\cl}{\text{Cl}}
\newcommand{\tr}{\text{trace}}
\newcommand{\rk}{\text{rank}}
\newcommand{\cn}{\text{cone}}
\newcommand{\dbt}{\text{\bf{d}}}
\newcommand{\dt}{\text{{dist}}}
\newcommand{\dtR}{\dt_{\R^+}(\h)}
\newcommand{\vs}{\vspace}
\newcommand{\hs}{\hspace}
\newcommand{\has}{\hat{\s}}
\newcommand{\nn}{\nonumber}
\newcommand{\li}{\left<}
\newcommand{\ri}{\right>}
\newcommand{\nor}{\|\cdot\|}
intro.tex
\vspace{-10pt}
\section{Introduction}

\vspace{-15pt}
\subsection{Motivation}
The Least Absolute Shrinkage and Selection Operator (LASSO) is a celebrated convex progam used to estimate sparse signals from noisy linear underdetermined observations. Given a vector of observations $\y = \A\x_0 + \z \in \R^m$ of an unknown, but $k$-\emph{sparse} (i.e., at most $k$ nonzero entries), signal 
%$\x_0\in\R^{n},n>m$,
$\x_0\in\R^{n}$,
 the $\ell_2$-LASSO\footnote{Also known as ``square-root LASSO" \cite{Belloni}. Please refer to \cite[Sec.~1.3]{OTH}.} produces the following estimate for $\x_0$:
\begin{align}\label{eq:LASSO}
\hspace{-10pt}\hat\x
%^{\la,\sigma}
 := \arg\min_{\x} \Lc(\x;\A,\z) :=\|\y - \A\x\|_2 + \frac{\la}{\sqrt{m}} \|\x\|_1.
\end{align}
Here, $\A\in\R^{m\times n}$ is the sensing matrix, $\z\in\R^m$ is the noise vector and $\la> 0$ is a regularizer parameter.  The LASSO has been long investigated from different perspectives and shown to enjoy unique properties, in terms of both computation and precision. Yet, some important asymptotic properties of it have not yet been fully understood. Our interest is on the \emph{exact} characterization of 
%the $\ell_2$-norm of 
the reconstruction error $\|\hat\x-\x_0\|_2$. 

% is a key ingredient of the so called Compressed Sensing literature. It has been long investigated from different perspectives and shown to enjoy unique properties, in terms of both computation and precision. Yet, some important asymptotic properties of LASSO have not yet been fully understood. This work derives an exact characterization of the error of the LASSO estimate when the sensing matrix has i.i.d Gaussian entries.

\vp
\subsection{Contribution}
\vp
We assume a generic setup in which the entries of the sensing matrix and the \emph{non-zero} entries of $\x_0$  are i.i.d  Gaussian. Also, the noise vector $\z$ is assumed to have entries i.i.d Gaussian with variance $\sigma^2$.
% entries $\Nn(0,1/m)$. The noise vector is also considered to be Gaussian with entries i.i.d $\Nn(0,\sigma^2)$. For the unknown signal $\x_0$ we assume it is $k$-sparse with fixed support set over which the entries are distributed i.i.d $\Nn(0,\sigma_x^2)$.
Under this assumption we derive an \emph{asymptotically exact} expression for the normalized squared error (NSE) $\|\hat\x-\x_0\|_2^2/\sigma^2$ of the $\ell_2$L-ASSO. 
%Our expression characterizes the behavior of the NSE as a function of the problem dimensions $n$, $m$ and $k$ and the value of the regularizer parameter $\la$.
% and the signal to noise ratio (SNR). 
In the low noise regime $\sigma^2\rightarrow 0$, our result reduces to simple and interpretable formulae.
% This expression can be used to show that the worst-case NSE occurs in the limit $\sigma\rightarrow 0$. Our analysis results in simple and precise formulae for this worst-case NSE.
Although our theoretical analysis requires an asymptotic setting in which the problem dimensions grow to infinity, our numerical illustrations suggest that the predictions be accurate already with problem dimensions ranging over only a few hundreds.  Also, we remark on our assumption on the Gaussian nature of the sensing matrix. This assumption has a long tradition in the statistics literature and sheds important insights \cite{MontanariLASSO}; the Gaussian ensemble has wonderful properties which make the analysis tractable, while at the same time many of the results 
%that are initially proved for the Gaussian ensemble are later shown to 
generalize to a wider class of distributions.
% (e.g. \cite{donoho2009observed,bayati2012universality}). A typical example of such a result, that was first proved for the Gaussian ensemble and was later shown to have universality properties is  the phase transition thresholds of the $\ell_1$-minimization in the Noiseless Compressed Sensing Literature \cite{Donoho,DonohoUniversality}.
%For example, in the Compressed Sensing Literature this assumption has allowed researchers to obtain tight characterizations of the phase transition phenomena  ...
The main technical tool used in our analysis is a gaussian comparison inequality due to Gordon \cite{Gor}. When combined with appropriate convexity assumptions, the inequality can be shown to be tight \cite{stojnic2013meshes,OTH,Allerton,tight}, which makes it ideal for our precise analysis.
% This observation is first attributed to Stojnic \cite{stojnic2013meshes} and was subsequently refined 

% Some of the core ideas were first introduced by Stojnic in \cite{StoLASSO}. %See also \Section{} for a discussion on related literature.


% COPIED FROM MONTANARI:
%While this setting is
%admittedly specific, the careful study of such matrix ensembles
%has a long tradition both in statistics and communications theory
%and has spurred many insights [16], [24]. Further, we carried out
%simulations on real data matrices with continuous entries (gene
%expression data) and binary feature matrices (hospital medical
%records). The results appear to be quite encouraging.


\vspace{-10pt}
\subsection{Relevant  Literature}
\vp
The LASSO was introduced by Tibshirani in \cite{TibLASSO} in the form
% who proposed solving 
\vp
\begin{align}
\hat\x = \arg\min_{\x} \|\y-\A\x\|_2 \text{ s.t. } \|\x\|_1\leq\|\x_0\|_1.\label{eq:conLASSO}
\end{align}
\vp
\eqref{eq:LASSO} is a regularized version of \eqref{eq:conLASSO}. An alternative to \eqref{eq:LASSO} solves  
\vspace{-8pt}
\begin{align}
\hat\x = \arg\min_{\x} \|\y-\A\x\|_2^2+ \tau\|\x\|_1.\label{eq:ell22LASSO}
\end{align}
Both this and \eqref{eq:LASSO} are variations of the same algorithm and Lagrange duality ensures that they both become equivalent
to the constrained optimization \eqref{eq:conLASSO} for proper choice of the regularizer parameters.
%The former version is arguably more popular in the literature than \eqref{eq:LASSO}, but
There are reasons to argue in favor of either of them \cite{Belloni,TOH14}, but they go beyond the scope of this paper. 
%The focus of this work is on \eqref{eq:LASSO}. }.
Early well-known bounds on the reconstruction error of the LASSO were  order-wise in nature (i.e. accurate only up to constant multiplicative factors) and derived based on RIP and Restricted Eigenvalue assumptions on the measurement matrix \cite{candes2006stable,candes2007dantzig,bickel,negahban2012unified,Belloni}. To the best of our knowledge, the first precise asymptotic evaluation of the limiting behavior of the LASSO reconstruction error is due to Bayati and Montanari \cite{MontanariLASSO}; they consider problem \eqref{eq:ell22LASSO}, i.i.d Gaussian sensing matrix $\A$ and use the Approximate Message Passing (AMP) framework. More recently, and closer to our work, Stojnic introduced an alternative framework that cleverly uses a celebrated gaussian comparison inequality due to Gordon \cite{Gor}; he applied this on \eqref{eq:conLASSO} and obtained precise characterizations for its worst-case NSE, which he showed to occur in the limit $\sigma^2\rightarrow 0$. The same framework was used in \cite{OTH} to generalize the results of \cite{StoLASSO} to arbitrary convex regularizer functions. Moreover, the authors in \cite{OTH} consider \eqref{eq:LASSO} and obtain simple, precise error formulae when $\sigma^2\rightarrow 0$. Our work, extends this result of \cite{OTH} in several directions for the case of sparse recovery. First, it holds for arbitrary values of the noise-variance $\sigma^2$; to our knowledge, this is the first such precise asymptotic result for \eqref{eq:LASSO} (\cite{MontanariLASSO} considers \eqref{eq:ell22LASSO}), and suggests the capabilities of the framework used.  Also, when $\sigma^2\rightarrow 0$, it recovers the result of \cite{OTH} and extends it on the range of values of $\la$ for which it holds. Finally, we believe that our result can be used to prove that the worst-case NSE of \eqref{eq:LASSO} occurs when $\sigma^2\rightarrow 0$. This would imply that the simple and interpretable expressions corresponding to that regime are tight bounds on the NSE for arbitrary noise levels. Some additional effort is required to prove this claim and is, thus, left for future work.

% in the case of sparse recovery. Our general result, can be used to yield useful conclusions. Specifically, when $\sigma^2\rightarrow 0$, we recover  the results of \cite{OTH} and also extend
%methodology

%The LASSO was introduced by Tibshirani in \cite{Tib}\footnote{More precisely, \cite{Tib} proposed solving 
%$\hat\x = \arg\min_{\x} \|\y-\A\x\|_2 \text{ s.t. } \|\x\|_1\leq\|\x_0\|_1$; \eqref{eq:LASSO} is a regularized version of this problem. An alternative to \eqref{eq:LASSO} solves for $\hat\x = \arg\min_{\x} \|\y-\A\x\|_2^2+ \tau\|\x\|_1$. Both this and \eqref{eq:LASSO} are variations of the same algorithm and Lagrange duality ensures that they both become equivalent
%to the constrained optimization for proper choice of the regularizer parameters.
%%The former version is arguably more popular in the literature than \eqref{eq:LASSO}, but
%There are reasons to argue in favor of either of them \cite{Belloni,TOH14}, but they go beyond the scope of this paper. The focus of this work is on \eqref{eq:LASSO}. }. Since then ...

%The original analysis of the LASSO has been carried out with sophisticated tools of random matrix theory. The pioneering studies of [] first showed the possibility of reliable data acquisition through random underdetermined sensing matrices  by investigating on the so called phase transition behavior of the LASSO in an ideal case, which led to interesting perfect recovery conditions. This strongly relied on the Restricted Isometry Property (RIP), which was later replaced by more general arguments on random matrices []. The perfect recovery condition has been substantially improved. However, the original approaches has been unsuccessful to provide a deeper insight. Thus, the questions such as the asymptotic behavior of error for the noisy LASSO have not been addressed until recently.   
%
%A recent discovery in [] illustrates that the previous findings for the i.i.d. Gaussian sensing matrices can be easily obtained by utilizing the so-called comparison inequalities. In fact, [] shows that the so-called Gordon's comparison Theorem tightly connects LASSO to a simpler so-called key optimization. With this approach, the authors succeeded to provide a bound on the error magnitude, which also characterizes the error in the high SNR case. However, the exact solution of the key optimization has not been provided yet.
%
%In this work, we show that the solution of the key optimization for large sensing matrices is determined by the solution of a two-dimensional deterministic optimization, called asymptotic key optimization (AKO) which can be numerically carried out. In this way, we find the exact numerical values for the asymptotic LASSO error. We demonstrate how the previous results on the error and perfect recovery can be successfully obtained from AKO. We also argue on the exactness of the bound given in []. The numerical results are verified by comparing to the simulated ones.

main.tex

% Template for ICASSP-2015 paper; to be used with:
%          spconf.sty  - ICASSP/ICIP LaTeX style file, and
%          IEEEbib.bst - IEEE bibliography style file.
% --------------------------------------------------------------------------
\documentclass{article}
\usepackage{spconf,amsmath,graphicx,amsfonts}

% Example definitions.
% --------------------

% Title.
% ------
\title{Precise Error Analysis of the $\ell_2$-LASSO}
%
% Single address.
% ---------------
\vspace{-10pt}
\name{ Christos Thrampoulidis$^*$
Ashkan Panahi$^\dagger$, Daniel Guo$^*$, Babak Hassibi$^*$ \thanks{The work of B. Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by the Office of Naval Research under the MURI grant N00014-08--0747, by the Jet Propulsion Lab under grant IA100076, by a grant from Qualcomm Inc., and by King Abdulaziz University.}
}
\vspace{-10pt}
\address{
* Department of Electrical Engeeniring, Caltech, Pasadena, USA\\
$\dagger$ Signal Processing Group, Chalmers University of Technology, Gothenburg, Sweden
}
%
% For example:
% ------------
%\address{School\\
%	Department\\
%	Address}
%
% Two addresses (uncomment and modify for two-address case).
% ----------------------------------------------------------
%\twoauthors
%  {A. Author-one, B. Author-two\sthanks{Thanks to XYZ agency for funding.}}
%	{School A-B\\
%	Department A-B\\
%	Address A-B}
%  {C. Author-three, D. Author-four\sthanks{The fourth author performed the work
%	while at ...}}
%	{School C-D\\
%	Department C-D\\
%	Address C-D}
%
\usepackage{enumerate}
\usepackage{amsmath,amssymb,algorithm,cite,cases,bm,float,graphicx,url}
\usepackage{pbox}
%\numberwithin{equation}{section}

\usepackage{amsthm}
%\theoremstyle{plain}
\newtheorem*{theorem*}{Theorem}
\newtheorem{theorem}{Theorem}
\newtheorem*{lemma*}{Lemma}
\newtheorem{lemma}{Lemma}


\newtheorem{defn}{Definition}[section]
\newtheorem{appdefn}{Definition}[subsection]

\newtheorem{fact}{Fact}[section]
\newtheorem{prop}{Property}[section]
\newtheorem{propo}{Proposition}[section]
\newtheorem{apppropo}{Proposition}[subsection]

\newtheorem{conj}{Conjecture}[section]

\newtheorem{thm}{Theorem}[section]
\newtheorem{appthm}{Theorem}[subsection]


\newtheorem{lem}{Lemma}[section]
\newtheorem{applem}{Lemma}[subsection]
\newtheorem{form}{Formula}
\newtheorem{cor}{Corollary}[section]
\newtheorem{pro}{Problem}[section]



\newcommand{\daniel}[1]{ \textcolor{red}{{\bf{Daniel:}} #1 }}
\newcommand{\chris}[1]{ \textcolor{blue}{{ \bf{Christos:}} #1 }}
\newcommand{\ashkan}[1]{ \textcolor{darkgreen}{{\bf{Ashkan:}} #1 }}\newcommand{\eqname}[1]
{ \textcolor{red}{ #1 }}

\usepackage{lipsum}
\usepackage{amsmath,amssymb,algorithm,cite,caption,cases,bm,float,graphicx,url,color}
\usepackage[hidelinks]{hyperref}
\usepackage{comment}
\usepackage{thm-restate, enumerate }

\definecolor{darkred}{RGB}{150,0,0}
\definecolor{darkgreen}{RGB}{0,150,0}
\definecolor{darkblue}{RGB}{0,0,200}
\hypersetup{colorlinks=true, linkcolor=darkred, citecolor=darkgreen, urlcolor=darkblue}

\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}

\usepackage[numbers]{natbib}


\newcommand{\keyopt}{key optimization}
\bibliographystyle{IEEETran}


%\addtolength{\oddsidemargin}{-1in}
%\addtolength{\evensidemargin}{-1in}
%\addtolength{\textwidth}{2in}
%\addtolength{\topmargin}{-1in}
%\addtolength{\textheight}{2in}

\input{commands}


\newcommand{\thename}{Gaussian min-max theorem}
\newcommand{\GMT}{GMT}



\begin{document}
%\title{\LARGE{\bf{%Precise Error Bounds for the Constrained LAD Estimator
%Asymptotically Exact Analysis the LASSO Error}}}
%%Other title possibilities
%%The risk of noisy linear inverse algorithms
%%
%%\vspace
%\author{
%%This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CIF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by a grant from Qualcomm Inc.
%%
%}

%\address{}
%\date{}
%


\maketitle
\begin{abstract} 
A classical problem that arises in numerous signal processing applications
%Consider the classical problem of 
asks for the reconstruction of an unknown, $k$-sparse signal $\x_0\in \R^n$ from underdetermined, noisy, linear measurements $\y=\A\x_0+\z\in \R^m$. One standard approach is to solve the following convex program $\hat\x=\arg\min_\x \|\y-\A\x\|_2 + \la \|\x\|_1$, which is  known as the $\ell_2$-LASSO. We assume that the entries of the  sensing matrix $\A$ and of the noise vector $\z$ are i.i.d Gaussian with variances $1/m$ and $\sigma^2$. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we \emph{precisely} characterize the limiting behavior of the normalized squared error $\|\hat\x-\x_0\|^2_2/\sigma^2$. Our numerical illustrations validate our theoretical predictions.


%A classical problem that arises in numerous signal processing applications
%asks for the reconstruction of an unknown, $k$-sparse signal $x_0\in R^n$ from underdetermined, noisy, linear measurements $y=Ax_0+z\in R^m$. One standard approach is to solve the following convex program $\hat x=\arg\min_x \|y-Ax\|_2 + \lambda \|x\|_1$, which is widely known as the LASSO. We assume that the entries of the  sensing matrix $A$ and of the noise vector $z$ are i.i.d Gaussian with variance $1/m$ and $\sigma^2$. In the large system limit when the problem dimensions grow to infinity, but in constant rates, we \emph{precisely} characterize the limiting behavior of the noise sensitivity $\|\hat x-x_0\|^2_2/\sigma^2$. Our numerical illustrations validate our theoretical predictions.


%The asymptotic analysis of the LASSO has been recently advanced utilizing a celebrated theorem of Gordon. It has been shown that the asymptotic behavior of the LASSO by a sensing matrix with independent identically distributed Gaussian entries is completely determined by a simpler optimization. In this paper, we show that the latter can also be replaced by a deterministic two-dimensional optimization, which is simple to evaluate by numerical means. We particularly provide the exact error magnitude for an arbitrary signal to noise ratio. We also connect the previous results to the proposed deterministic optimization by analysis and provide some further implications.      
\end{abstract}
 %ASYMPTOTICALLY EXACT
 
 \begin{keywords}
\small{LASSO, square-root LASSO, normalized squared error, sparse recovery, Gaussian min-max theorem}
%random matrix theory 
\end{keywords}

% ------------------------------------------------------------------------------------------------------------------- %
\input{intro}
\input{analysis}
\input{results}
\vp
%\section{Conclusion}
%We have precisely characterized the reconstruction performance of the LASSO in \eqref{eq:LASSO} for any value of the noise variance $\sigma$. 
%\input{gorOpt}

%\input{app}

%\input{proof}

%\input{application}%\label{sec:app}

%\bibliographystyle{apa}

\newpage
\bibliography{compbib}

%\input{appendix}

%\input{tech}


\end{document}
results.tex

\vspace{-10pt}
\section{Results}



\vspace{-8pt}
\subsection{Arbitrary SNR Values}
\vspace{-7pt}
For the statement of our main result, recall \eqref{eq:D} and further consider the definitions in \eqref{eq:defn}. We also need the following.
%\begin{align*}
%\hspace{-10pt}&\Dlf := k(1+\la^2) + (n-k)\rho(1,\la),
%\Clf := -\frac{\la}{2}\frac{\partial\Dlf}{\partial\la},\\
%&\psi(\la) := Q^{-1}\left( \frac{1}{2} + \frac{m-\Dlf-\Clf}{2k} \right)
%\end{align*}
\vspace{-9pt}
\begin{defn}[$\lac^\sigma$]\label{def:lac}
Define $\lac^\sigma$ as the unique solution of the equation $f(x,\frac{x}{\psi(x)})=0$. Further, define  $\lac^{0} := Q^{-1}\left(\frac{1}{2}\frac{m-k}{n-k}\right)$ and
\vspace{-14pt}
\begin{align*}
\lac^{min} := \begin{cases}
Q^{-1}\left(\frac{1}{2}\frac{m}{n-k}\right) & \text{ if } m<n-k,\\
0 & \text{else}.
\end{cases}
\end{align*}
 \end{defn}
%\begin{propo}
%Define $\lac^{0} := Q^{-1}\left(\frac{1}{2}\frac{m-k}{n-k}\right)$ and
%\begin{align*}
%\lac^{\infty} := \begin{cases}
%Q^{-1}\left(\frac{1}{2}\frac{m}{n-k}\right) & \text{ if } m<n-k,\\
%0 & \text{else.},
%\end{cases}
%\end{align*}
%Then,

\vspace{-10pt}
\noindent It can be shown that for all $\sigma>0$: $\lac^{min}\leq\lac^{\sigma}\leq\lac^{0}$.
%\end{propo}


%\begin{table*}
%\begin{align}
%\hspace{-10pt}&\Dlf := k(1+\la^2) + (n-k)\rho(1,\la),\quad
%\Clf := -\frac{\la}{2}\frac{\partial\Dlf}{\partial\la}, \quad\psi(\la) := Q^{-1}\left( \frac{1}{2} + \frac{m-\Dlf-\Clf}{2k} \right),\nn\\
%&f(\la,\phi) := m- \Dlf + m{\sigma^2}(1-\phi^2) + k\left(\phi^2 - \la^2- 2\right)\left(2Q\left(\frac{\la}{\phi}\right)-1\right) +  k \sqrt{\frac{2}{\pi}}{\lambda\phi}\exp\left(-\frac{\la^2}{2\phi^2}\right). &
%\end{align}
%\protect\caption{Long equation}
%\label{tab:long-eq}
%\end{table*}
\vspace{-5pt}
\begin{thm}\label{thm:main}
 Let $\hat\x^{\la,\sigma}$ be the solution of the LASSO in \eqref{eq:LASSO}.
%  and $\Lc(\hat\x^{\la,\sigma})$ denote its optimal cost. 
  Recall the definitions of $f$ and $\lac^\sigma$ in \eqref{eq:defn} and Definition \ref{def:lac}.  Let $\lah := \max\{\la,\lac^\sigma\}$ and $q_*(\alpha) = \sqrt{1+\frac{m}{\sigma^2(m+\alpha^2)}}$. Denote $\alpha_*$ the unique solution of the equation $f\left(\lah, q_*(\alpha)\right)=0$ with respect to $\alpha$. Then,  the following limit holds in probability:
% \begin{itemize}
% \item $\lim_{n\rightarrow\infty}\frac{\|\hat\x^{\la,\sigma}-\x_0\|_2^2}{m\sigma^2}=\alpha_*,$
%% \item $\lim_{n\rightarrow\infty}\frac{1}{m}\Lc(\x^{\la,\sigma})\approx \frac{1}{\sqrt{m}}\Dc\left(\sigma\alpha_*, p_*(\sigma\alpha_*), \la/\lah\right)$.
% \end{itemize}
$\lim_{n\rightarrow\infty}\frac{\|\hat\x^{\la,\sigma}-\x_0\|_2}{\sigma\sqrt{m}}=\alpha_*.$
\end{thm}

\vspace{-20pt}
\subsection{Asymptotic NSE}\label{sec:as}
\vspace{-6pt}
Here we consider the case $\sigma^2\rightarrow 0$. 
%Our result recovers and extends on \cite[Theorem 3.2]{OTH} in the case of sparse recovery. \vspace{-5pt}
\vp
\begin{thm}\label{thm:main2}
% Let $\hat\x^{\la,0}$ be the solution of the LASSO in \eqref{eq:LASSO} and $\Lc(\hat\x^{\la,0})$ denote its optimal cost, in the limit as $\sigma\rightarrow 0$. 
Let $\lah := \max\{\la,\lac^0\}$. 
If  $m\geq \Dc(\lah)$, then the following limit holds in probability
% \begin{itemize}
% \item $\lim_{\sigma\rightarrow 0}\lim_{n\rightarrow\infty}\frac{\|\hat\x^{\la,0}-\x_0\|_2}{\sigma\sqrt{m}} = \frac{\sqrt{\Db(\lah)}}{\sqrt{m-\Db(\lah)}} ,$
% \item $\Lc(\x^{\la,\sigma})\approx (\la/\lah)
%% \frac{\la}{\lah}
% \sqrt{m}\sqrt{m-\Db(\lah)}  +\la k \sqrt\frac{2}{\pi}.$
% \end{itemize}
\vspace{-14pt}
$$\lim_{n\rightarrow\infty}\lim_{\sigma\rightarrow 0}\frac{\|\hat\x^{\la,0}-\x_0\|_2}{\sigma\sqrt{m}} = \sqrt\frac{{\Db(\lah)}}{{m-\Db(\lah)}} .$$
\end{thm}
\vspace{-7pt}
When $\la>\lac$, Theorem \ref{thm:main2} recovers the result of \cite[Theorem 3.2]{OTH};
%\cite{OTH} proves the formula of the theorem for $\la>\lac$; 
adding to this, we are  able to characterize the behavior when $\la<\lac$.
%Theorem \ref{thm:main2} additionally characterizes the behavior when $\la<\lac$.
 The theorem suggests that stable recovery is possible only when $m>\Dc(\lah)$. In particular, we require that at least $m>\min_{\la>0}\Dlf$. A recent line of work \cite{Sto,Cha,TroppEdge,stojnic2013upper}, has shown that $\min_{\la>0}\Dlf$ precisely characterizes the minimum number $m$ of required measurements for exact recovery of sparse signals under \emph{noiseless} linear measurements. Also, the minimum of the formula that appears in the theorem is achieved at $\la_{best}:=\arg\min_{\la>0}\Dlf$. We refer the reader to Figure \ref{fig:main} for an illustration of $\lac^0,\labb$ and to  \cite[Section 4.2]{OTH} for a detailed further discussion.


%\chris{Comment on $\min\Dlf$ being the phase transition threshold in noiseless CS.}

\vspace{-10pt}
\section{Simulation Results and Conclusion}

\vspace{-15pt}
\begin{figure}[!h]
\centering
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{aiai2}
  \caption{\footnotesize{optimal cost}}
  \label{fig:IIIA_1}
\end{subfigure}%
\\
\vspace{-2pt}
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=0.75\linewidth]{aiai1}
  \caption{\footnotesize{normalized error}}
  \label{fig:IIIA_2}
\end{subfigure}
\vspace{-6pt}
  \caption{\footnotesize{$n=500$, $m = 150$, $k = 20$. Averages over 20 realizations.}}
\label{fig:main}
\end{figure}
\vspace{-10pt}
In  Figure \ref{fig:main}, observe the close agreement of the simulation results to the  predictions of Theorems \ref{thm:main} and \ref{thm:main2} (for the case $\sigma^2=10^{-4}$, we used Theorem \ref{thm:main2} for the prediction). Refer to Section \ref{sec:as} for the definitions of $\lac^0,\la_{best}$; $\la_{max}$ is such that $m<\Dlf$ for all $\la>\la_{max}$. Our expressions are accurate for problem sizes on the order of a few hundreds and valid for all values of $\sigma^2$. In Figure \ref{fig:IIIA_2}, the worst-case NSE occurs 
in the small noise-variance regime. We believe that this claim can be proved using Theorems \ref{thm:main} and \ref{thm:main2}.
main.bbl
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@rmstyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand\BIBentrySTDinterwordspacing{\spaceskip=0pt\relax}
\providecommand\BIBentryALTinterwordstretchfactor{4}
\providecommand\BIBentryALTinterwordspacing{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand\BIBforeignlanguage[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}

\bibitem{Belloni}
A.~Belloni, V.~Chernozhukov, and L.~Wang, ``Square-root lasso: pivotal recovery
  of sparse signals via conic programming,'' \emph{Biometrika}, vol.~98, no.~4,
  pp. 791--806, 2011.

\bibitem{OTH}
S.~Oymak, C.~Thrampoulidis, and B.~Hassibi, ``The squared-error of generalized
  lasso: A precise analysis,'' \emph{arXiv preprint arXiv:1311.0830}, 2013.

\bibitem{MontanariLASSO}
M.~Bayati and A.~Montanari, ``The lasso risk for gaussian matrices,''
  \emph{Information Theory, IEEE Transactions on}, vol.~58, no.~4, pp.
  1997--2017, 2012.

\bibitem{Gor}
Y.~Gordon, \emph{On Milman's inequality and random subspaces which escape
  through a mesh in $\mathbb{R}^n$}.\hskip 1em plus 0.5em minus 0.4em\relax
  Springer, 1988.

\bibitem{stojnic2013meshes}
M.~Stojnic, ``Meshes that trap random subspaces,'' \emph{arXiv preprint
  arXiv:1304.0003}, 2013.

\bibitem{Allerton}
C.~Thrampoulidis and B.~Hassibi, ``Estimating structured signals in sparse
  noise: A precise noise sensitivity analysis,'' in \emph{Communication,
  Control, and Computing (Allerton), 2014 52nd Annual Allerton Conference
  on}.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, 2014, pp. 866--873.

\bibitem{tight}
C.~Thrampoulidis, S.~Oymak, and B.~Hassibi, ``A tight version of the gaussian
  min-max theorem in the presence of convexity,'' \emph{arXiv preprint
  arXiv:1408.4837}, 2014.

\bibitem{TibLASSO}
R.~Tibshirani, ``Regression shrinkage and selection via the lasso,''
  \emph{Journal of the Royal Statistical Society. Series B (Methodological)},
  pp. 267--288, 1996.

\bibitem{TOH14}
C.~Thrampoulidis, S.~Oymak, and B.~Hassibi, ``Simple error bounds for
  regularized noisy linear inverse problems,'' \emph{Information Theory, 2014.
  ISIT 2014. Proceedings. International Symposium on}.

\bibitem{candes2006stable}
E.~J. Candes, J.~K. Romberg, and T.~Tao, ``Stable signal recovery from
  incomplete and inaccurate measurements,'' \emph{Communications on pure and
  applied mathematics}, vol.~59, no.~8, pp. 1207--1223, 2006.

\bibitem{candes2007dantzig}
E.~Candes and T.~Tao, ``The dantzig selector: Statistical estimation when p is
  much larger than n,'' \emph{The Annals of Statistics}, pp. 2313--2351, 2007.

\bibitem{bickel}
P.~J. Bickel, Y.~Ritov, and A.~B. Tsybakov, ``Simultaneous analysis of lasso
  and dantzig selector,'' \emph{The Annals of Statistics}, vol.~37, no.~4, pp.
  1705--1732, 2009.

\bibitem{negahban2012unified}
S.~N. Negahban, P.~Ravikumar, M.~J. Wainwright, and B.~Yu, ``A unified
  framework for high-dimensional analysis of $ m $-estimators with decomposable
  regularizers,'' \emph{Statistical Science}, vol.~27, no.~4, pp. 538--557,
  2012.

\bibitem{StoLASSO}
M.~Stojnic, ``A framework to characterize performance of lasso algorithms,''
  \emph{arXiv preprint arXiv:1303.7291}, 2013.

\bibitem{Ledoux}
M.~Ledoux and M.~Talagrand, \emph{Probability in Banach Spaces: isoperimetry
  and processes}.\hskip 1em plus 0.5em minus 0.4em\relax Springer, 1991,
  vol.~23.

\bibitem{Roc70}
R.~T. Rockafellar, \emph{Convex analysis}.\hskip 1em plus 0.5em minus
  0.4em\relax Princeton university press, 1997, vol.~28.

\bibitem{Sto}
M.~Stojnic, ``Various thresholds for $\ell_1$-optimization in compressed
  sensing,'' \emph{arXiv preprint arXiv:0907.3666}, 2009.

\bibitem{Cha}
V.~Chandrasekaran, B.~Recht, P.~A. Parrilo, and A.~S. Willsky, ``The convex
  geometry of linear inverse problems,'' \emph{Foundations of Computational
  Mathematics}, vol.~12, no.~6, pp. 805--849, 2012.

\bibitem{TroppEdge}
D.~Amelunxen, M.~Lotz, M.~B. McCoy, and J.~A. Tropp, ``Living on the edge: A
  geometric theory of phase transitions in convex optimization,'' \emph{arXiv
  preprint arXiv:1303.6672}, 2013.

\bibitem{stojnic2013upper}
M.~Stojnic, ``Upper-bounding $\ell_1$-optimization weak thresholds,''
  \emph{arXiv preprint arXiv:1303.7289}, 2013.

\end{thebibliography}
