A framework to characterize performance of LASSO algorithms

Introduction

In recent years the problem of finding sparse solutions of under-determined systems of linear equations attracted enormous attention. Applications seem vast and as if they are growing almost on a daily basis (see, e.g. and references therein). Given a substantial interest in the problem (and especially that it is coming from a variety of different fields), one may assume that designing efficient algorithms that would solve it could be of far-reaching importance. To that end, we believe that a precise mathematical understanding of the phenomena that make certain algorithms work well would help solidify belief in their success in current and future applications. Moreover, it is possible that down the road it can also help expand further the range of their applications.

Moving long the same lines, we in this paper focus on studying mathematical properties of under-determined systems of linear equations and certain algorithms used to solve them. We start the story by introducing an idealized version of the problem that we plan to study. In its simplest form it amounts to finding a $k$-sparse ${\bf x}$ such that

where $A$ is an $m\times n$ ($m<n$) matrix and ${\bf y}$ is an $m\times 1$ vector (see Figure 1; here and in the rest of the paper, under $k$-sparse vector we assume a vector that has at most $k$ nonzero components). Of course, the assumption will be that such an ${\bf x}$ exists (clearly, the case of real interest is $k<m$). To make writing in the rest of the paper easier, we will assume the so-called linear regime, i.e. we will assume that $k=\beta n$ and that the number of equations is $m=\alpha n$ where $\alpha$ and $\beta$ are constants independent of $n$ (more on the non-linear regime, i.e. on the regime when $m$ is larger than linearly proportional to $k$ can be found in e.g. ).

If one has the freedom to design matrix $A$ then the results from demonstrated that the techniques from coding theory (based on coding/decoding of Reed-Solomon codes) can be employed to determine any $k$-sparse ${\bf x}$ in (1) for any $0<\alpha\leq 1$ and any $\beta\leq\frac{\alpha}{2}$ in polynomial time. It is relatively easy to show that under the unique recoverability assumption $\beta$ can not be greater than $\frac{\alpha}{2}$. Therefore, as long as one is concerned with the unique recovery of $k$-sparse ${\bf x}$ in (1) in polynomial time the results from are optimal. The complexity of algorithms from is roughly $O(n^{3})$. In a similar fashion one can, instead of using coding/decoding techniques associated with Reed/Solomon codes, design the matrix and the corresponding recovery algorithm based on the techniques related to coding/decoding of Expander codes (see e.g. and references therein). In that case recovering ${\bf x}$ in (1) is significantly faster for large dimensions $n$. Namely, the complexity of the techniques from e.g. (or their slight modifications) is usually $O(n)$ which is clearly for large $n$ significantly smaller than $O(n^{3})$. However, the techniques based on coding/decoding of Expander codes usually do not allow for $\beta$ to be as large as $\frac{\alpha}{2}$.

As is then shown in if $\alpha$ and $n$ are given, $A$ is given and satisfies the restricted isometry property (RIP) (more on this property the interested reader can find in e.g. ), then any unknown vector ${\bf x}$ with no more than $k=\beta n$ (where $\beta$ is a constant dependent on $\alpha$ and explicitly calculated in ) non-zero elements can indeed be recovered by solving (2). In a statistical and large dimensional context in and later in for any given value of $\beta$ the exact value of the maximum possible $\alpha$ was determined.

As we mentioned earlier the above scenario is in a sense idealistic. Namely, it assumes that ${\bf y}$ in (2) was obtained through (1). On the other hand in many applications only a noisy version of $A{\bf x}$ may be available for ${\bf y}$ (this is especially so in measuring type of applications) see, e.g. . When that happens one has the following equivalent to (1) (see, Figure 2)

where ${\bf v}$ is an $m\times 1$ vector (often dubbed as the noise vector; the so-called ideal case presented above is of course a special case of the noisy case).

Finding the $k$-sparse ${\bf x}$ in (3) is now incredibly hard. Basically, one is looking for a $k$-sparse ${\bf x}$ such that (3) holds and on top of that ${\bf v}$ is unknown. Although the problem is hard there are various heuristics throughout the literature that one can use to solve it approximately. Below we restrict our attention to two groups of algorithms that we believe are the most relevant to the results that we will present.

To introduce a bit or tractability in finding the $k$-sparse ${\bf x}$ in (3) one usually assumes certain amount of knowledge about either ${\bf x}$ or ${\bf v}$. As far as tractability assumptions on ${\bf v}$ are concerned one typically (and possibly fairly reasonably in applications of interest) assumes that $\|{\bf v}\|_{2}$ is bounded (or highly likely to be bounded) from above by a certain known quantity. The following second-order cone programming (SOCP) analogue to (2) is one of the approaches that utilizes such an assumption (see, e.g. )

where, $r$ is a quantity such that $\|{\bf v}\|_{2}\leq r$ (or $r$ is a quantity such that $\|{\bf v}\|_{2}\leq r$ is say highly likely). For example, in a statistical context is assumed and based on the statistics of ${\bf v}$, $r$ was chosen such that $\|{\bf v}\|_{2}\leq r$ happens with overwhelming probability (as usual, under overwhelming probability we in this paper assume a probability that is no more than a number exponentially decaying in $n$ away from $1$). Given that (4) is now among few almost standard choices when it comes to finding the ${\bf x}$-sparse in (3), the literature on its properties is vast (see, e.g. and references therein). Also, given that this SOCP will not be the main topic of this paper we below briefly mention only what we consider to be the most influential work on this topic in recent years. Namely, in the authors analyzed performance of (4) and showed a result similar in flavor to the one that holds in the ideal - noiseless - case. In a nutshell the following was shown in : let ${\bf x}$ be a $\beta n$-sparse vector such that (3) holds and let ${\bf x}_{socp}$ be the solution of (4). Then $\|{\bf x}_{socp}-{\bf x}\|_{2}\leq Cr$ where $\beta$ is a constant independent of $n$ and $C$ is a constant independent of $n$ and of course dependent on $\alpha$ and $\beta$. This result in a sense establishes a noisy equivalent to the fact that a linear sparsity can be recovered from an under-determined system of linear equations. In an informal language, it states that a linear sparsity can be approximately recovered in polynomial time from a noisy under-determined system with the norm of the recovery error guaranteed to be within a constant multiple of the noise norm. Establishing such a result is, of course, a feat in its own class, not only because of its technical contribution but even more so because of the amount of interest that it generated in the field.

In this paper we will also consider an approximate recovery of the $k$-sparse ${\bf x}$ in (3). However, instead of the above mentioned SOCP we will focus on a group of highly successful algorithms called LASSO (the LASSO algorithms, as well as the SOCP ones, are of course well known in the statistics community and there is again a vast literature that covers their performance (see, e.g. and references therein). There are many variants of LASSO but the following one is probably the most well known

$\lambda_{lasso}$ in (5) is a parameter to be chosen based on the amount of pre-knowledge one may have about $A$, ${\bf v}$, and/or ${\bf x}$. The results that relate to the characterization of the approximation error of (5) that are similar to the SOCP ones mentioned above can be established (see, e.g. ). Of course, characterizing the performance of the recovery algorithm through the norm-2 of the error vector is only one possible way among many (more on other measures of performance can be found in e.g. ). In this paper we will develop a novel framework for performance characterization of the LASSO algorithms. Among other things, in a statistical context, the framework will enable us to provide a precise characterization of the norm-2 of the approximation error of the LASSO algorithms.

While our main focus in this paper are algorithms from the LASSO group we mention that besides the SOCP and LASSO algorithms there are of course various other algorithms/heuristics that have been suggested as possible alternatives throughout the literature in recent years. Such an alternative that gained certain amount of popularity is for example the so-called Dantzig selector introduced in . The Dantzig selector amounts to solving the following optimization problem

where $C_{Dan}$ is a carefully chosen parameter that of course should depend on $A,{\bf v}$, and/or ${\bf x}$. As a linear program the Danzig selector promises to be faster than SOCP or LASSO which are both quadratic programs. On the other hand recent improvements in numerical implementations of LASSO’s and their solid approximate recovery abilities make them quite competitive as well (more on a thorough discussion/comparison, advantages/disdvatnages of the Dantzig selector and the LASSO algorithms can be found in e.g. ).

To facilitate the exposition and the easiness of following we will present our framework on a version of the LASSO from (5). Namely, we will consider,

Before we proceed further we briefly summarize the organization of the rest of the paper. In Section 2, we present a statistical framework for the performance analysis of the LASSO algorithms. To demonstrate its power we towards the end of Section 2, for any given $\alpha$ and $\beta$, compute the worst case norm-2 of the error that (6) makes when used for approximate recovery of general sparse signals ${\bf x}$ from (3). In Section 3 we then specialize results from Section 2 to the so-called signed vectors ${\bf x}$. In Section 4 we discuss how the LASSO from (6) can be connected to the LASSO from (5). In Section 5 we demonstrate that there is an SOCP algorithm (similar to the one given in (4)) that achieves the same performance as do (6) and a corresponding (5). In Section 6 we present results that we obtained through numerical experiments. Finally, in Section 7 we discuss obtained results.

LASSO’s performance analysis framework – general 𝐱𝐱{\bf x}

Once we establish the framework it will be clear that it can be used to characterize many of the LASSO features. We will defer these details to a collection of forthcoming papers. In this paper we will present only a small application that relates to a classical question of quantifying the approximation error that (6) makes when used to recover any $k$-sparse ${\bf x}$ that satisfies (3) and is from a set of ${\bf x}$’s with a given fixed location of nonzero elements and a given fixed combination of their signs.

Before proceeding further we will introduce a few definitions that will be useful in formalizing this application as well as in conducting the entire analysis. As it is natural we start with the solution of (6). Let $\hat{{\bf x}}$ be the solution of (6) and let ${\bf w}_{lasso}\in R^{n}$ be such that

for an arbitrarily small constant $\epsilon$. However, before doing so we will first present the general framework. The framework that we will present will center around finding the optimal value of the objective function in (6) (of course in a probabilistic context). In the first of the following two subsections we will create a lower bound on this optimal value. We will then afterwards in the second of the subsections create an upper bound on this optimal value. Naturally in the third subsection we will show that the two bounds actually match. To make further writing easier and clearer we set already here

In this section we present the part of the framework that relates to finding a “high-probability” lower bound on $\zeta_{obj}$. To make arguments that will follow less tedious we will make an assumption that is significantly weaker than what we will eventually prove. Namely, we will assume that there is a (if necessary, arbitrarily large) constant $C_{\bf w}$ such that

To make our arguments flow more naturally, one should probably provide a direct proof of this statement right here. However, given the difficulty of the task ahead we refrain from that and assume that the statement is correct. Roughly speaking, what we assume is that $\|{\bf w}_{lasso}\|_{2}$ is bounded by an arbitrarily large constant (of course we hope to create a machinery that can prove much more than (11)).

where $A_{{\bf v}}=\begin{bmatrix}-A&{\bf v}\end{bmatrix}$ is now an $m\times(n+1)$ random matrix with i.i.d. standard normal components. Let

We now state a lemma from that will be of use in what follows.

() Let $A$ be an $m\times n$ matrix with i.i.d. standard normal components. Let ${\bf g}$ and ${\bf h}$ be $m\times 1$ and $n\times 1$ vectors, respectively, with i.i.d. standard normal components. Also, let $g$ be a standard normal random variable and let $\Phi\subset R^{n}$ be an arbitrary subset. Then for all choices of real $\psi_{\phi}$

In what follows we will analyze the following probability

which is of course nothing but the probability on the left-hand side of the inequality in (19). We will essentially show that for certain $\zeta_{obj}^{(l)}$ this probability is close to $1$. That will rather obviously imply that we have a “high probability” lower bound on $\zeta_{obj}$. To that end, we first note that the maximization over ${\bf a}$ is trivial and one obtains

To facilitate the exposition that will follow let

In this section we compute $\xi(\sigma,{\bf g},{\bf h})$. We first rewrite the optimization problem from (22) in the following possibly clearer form

To remove the absolute values we introduce auxiliary variables ${\bf t}_{i},1\leq i\leq n$ and transform the above problem to

The Lagrange dual of the above problem then becomes

After rearranging the terms we further have

After a few further arrangements we finally have

Setting $(\nu-\lambda_{i}^{(1)}-\lambda_{i}^{(2)})=0,1\leq i\leq n$, (to insure that the dual is bounded) and combining (24) and (27) is enough to obtain

where we of course use the fact that the strict duality obviously holds. After removing the minimization over ${\bf t}$ we have

The inner minimization over ${\bf w}$ is now doable. Setting the derivatives with respect to ${\bf w}_{i}$ to zero one obtains

where $\lambda^{(1)}=[\lambda_{1}^{(1)},\lambda_{2}^{(1)},\dots,\lambda_{n}^{(1)}]^{T}$, $\lambda^{(2)}=[\lambda_{1}^{(2)},\lambda_{2}^{(2)},\dots,\lambda_{n}^{(2)}]^{T}$. From (31) one then has

where ${\bf w}_{sol}$ is of course the solution of the inner minimization over ${\bf w}$. Now, one should note that (34) and (35) are of course possible only if $\|{\bf g}\|_{2}+\gamma-\|{\bf h}+\lambda^{(1)}-\lambda^{(2)}\|_{2}\geq 0$. Later in the paper we will recognize, that for $\lambda^{(1)}$ and $\lambda^{(2)}$ that are optimal in (29), validity of this condition essentially implies the regime (in $(\alpha,\beta)$ plane) where the worst-case $\|{\bf w}\|_{2}$ is finite with overwhelming probability (or equivalently, if for such $\lambda^{(1)}$ and $\lambda^{(2)}$ the condition is not valid then for the corresponding ($\alpha,\beta$) the worst-case $\|{\bf w}\|_{2}$ is infinite with overwhelming probability). Plugging the value of ${\bf w}_{sol}$ from (35) back in (29) gives

Let ${\bf z}^{(1)}=[1,1,\dots,1]^{T}$. By plugging the constraint $\lambda^{(1)}=\nu{\bf z}^{(1)}-\lambda^{(2)}$ back into the objective function and making sure that $\nu-\lambda_{i}^{(2)}\geq 0,1\geq i\geq n$, one can remove $\lambda^{(1)}$ from the above optimization and get the following

After a simple scaling of $\lambda^{(2)}$ one finds that the following is an equivalent to (38)

Now, the maximization over $\gamma$ can be done. After setting the derivative to zero one finds

where of course $\gamma_{opt}$ would be the solution of (39) only if larger than or equal to zero. Alternatively of course $\gamma_{opt}=0$. Now, based on these two scenarios we distinguish two different optimization problems:

The “overwhelming” optimization is the equivalent to (39) if for its optimal values $\hat{\nu}$ and $\widehat{\lambda^{(2)}}$ holds

We now summarize in the following lemma the results of this subsection.

Moreover, let $\hat{{\bf w}}$ be the solution of (22). Then

Let $f_{lip}(\cdot):R^{n}\longrightarrow R$ be a Lipschitz function such that $|f_{lip}({\bf a})-f_{lip}({\bf b})|\leq c_{lip}\|{\bf a}-{\bf b}\|_{2}$. Let ${\bf a}$ be a vector comprised of i.i.d. zero-mean, unit variance Gaussian random variables and let $\epsilon_{lip}>0$. Then

Further, let ${\bf w}_{lip}^{(1)}$ be the solution of the minimization in (50). Then, clearly

where $({\bf w}_{lip}^{(1)})_{i}$ is the $i$-th index of ${\bf w}_{lip}^{(1)}$. In an analogous fashion set

and let ${\bf w}_{lip}^{(2)}$ be the solution of the minimization in (51). Then again clearly

where of course $({\bf w}_{lip}^{(2)})_{i}$ is the $i$-th index of ${\bf w}_{lip}^{(2)}$. Now assume that $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})\neq f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$ (if they are equal we are trivially done). Further let $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})<f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$ (the rest of the argument of course can trivially be flipped if $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})>f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$). We then have

where as usual $\epsilon_{1}^{(norm)}>0$, $\epsilon_{2}^{(norm)}>0$, and $\epsilon_{1}^{({\bf w})}>0$ are arbitrarily small constants and $\epsilon_{3}^{(norm)}$, $\epsilon_{4}^{(norm)}$, and $\epsilon_{2}^{({\bf w})}$ are constant dependent on $\epsilon_{1}^{(norm)}>0$, $\epsilon_{2}^{(norm)}>0$, and $\epsilon_{1}^{({\bf w})}>0$, respectively, but independent of $n$.

Now, we return to the probabilistic analysis of (21). Combining (21), (22), and (49) we have

Since ${\bf h}_{n+1}$ is a standard normal one easily has $P({\bf h}_{n+1}\sigma\geq-\epsilon_{1}^{({\bf h})}\sqrt{n})\geq 1-e^{-\epsilon_{2}^{({\bf h})}n}$ where $\epsilon_{1}^{({\bf h})}>0$ is an arbitrarily small constant and $\epsilon_{2}^{({\bf h})}$ is a constant dependent on $\epsilon_{1}^{({\bf h})}$ and $\sigma$ but independent on $n$. By choosing

one then from (LABEL:eq:probanalcont1) has

As stated after (20), (58) is conceptually enough to establish a “high probability” lower bound on $\zeta_{obj}$. The next few steps that formally do so are rather obvious but we include them for the completeness. Combining (19) and (58) we obtain

where $\zeta_{obj}^{(l)}$ is as in (57). Now, one further has

Since $g$ is a standard normal one easily again has $P(g\sqrt{C_{\bf w}^{2}+\sigma^{2}}\leq\epsilon_{1}^{(g)}\sqrt{n})\geq 1-e^{-\epsilon_{1}^{g)}n}$ where $\epsilon_{1}^{(g)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(g)}$ is a constant dependent on $\epsilon_{1}^{(g)}$, $\sigma$, and $C_{\bf w}$ but independent on $n$. Applying this to the first term on the right hand side of the above inequality one obtains

Now let $\zeta_{obj}^{lower}=\zeta_{obj}^{l}-\epsilon_{1}^{(g)}\sqrt{n}$. From (57) then obviously

Also let $\epsilon_{lower}$ be a constant such that

Then a combination of (11), (59), (60), (61), (62), and (63) gives

We summarize the results from this subsection in the following lemma.

where $A_{\bf v}$ is as defined right after (14). If we can show that with overwhelming probability the objective value of the above optimization problem is negative then $r$ will be a valid “high probability” upper-bound on $\zeta_{obj}$. Moreover, it will be achieved by a ${\bf w}$ for which it will hold that $\|{\bf w}\|_{2}\leq C_{{\bf w}_{up}}$.

We now proceed in a fashion similar to the one from Subsection 2.1.1. To remove the absolute values we introduce auxiliary variables ${\bf t}_{i},1\leq i\leq n$, and transform the above problem to

We also slightly modify the first of the constraints from (67) in the following way

The Lagrange dual of the above problem then becomes

where $\nu^{(1)}$ is $1\times m$ row vector of Lagrange variables and $\lambda^{(1)},\lambda^{(2)}$ are as in previous sections. After rearranging terms we further have

After a few further arrangements we finally have

Setting $(\nu-\lambda_{i}^{(1)}-\lambda_{i}^{(2)})=0,1\leq i\leq n$, (to insure that the dual is bounded) we have

Finally we can write a dual problem to (69)

where we of course use the fact that the strict duality obviously holds. Now, we minimize over ${\bf w}$ by setting the derivatives to zero

Plugging (75) back in (73) we further have

Now, we minimize ${\cal L}(\lambda^{(1)},\lambda^{(2)},\nu^{(1)},\gamma_{1},\gamma_{2},{\bf b})$ over ${\bf b}$ by setting the derivatives to zero

After doing the trivial maximization over $\gamma_{1}$ and $\gamma_{2}$ one obtains

We rewrite (82) in a slightly more convenient form

Any $r$ such that $\lim_{n\rightarrow}P(f_{obj}^{(up)}\geq 0)=1$ is then a valid “high-probability” upper bound.

We now introduce a refinement of a lemma from which itself is a slightly modified Lemma 18 (Lemma 18 is of course the backbone of the escape through a mesh theorem utilized in ).

Let $A$ be an $m\times n$ matrix with i.i.d. standard normal components. Let ${\bf g}$ and ${\bf h}$ be $m\times 1$ and $(n+1)\times 1$ vectors, respectively, with i.i.d. standard normal components. Also, let $g$ be a standard normal random variable and let $\Lambda$ be a set such that $\Lambda=(\lambda^{(2)}|0\leq\lambda_{i}^{(2)}\leq 1,1\leq i\leq n)$. Then

with $\epsilon_{3}^{(g)}>0$ being an arbitrarily small constant independent of $n$. The left-hand side of the inequality in (85) is then the following probability of interest

After solving the inner maximization over ${\bf a}$ and pulling out $\|\nu\|_{2}$ one has

After minimization of the second term over a unit norm vector we further have

Now we change variables so that $\nu=\frac{1}{\|\nu^{(1)}\|_{2}}$ and $\lambda^{(2)}=\frac{2\lambda^{(2)}}{\|\nu^{(1)}\|_{2}}$ and redefine $\Lambda$ by setting

We also recall that ${\bf z}^{(1)}$ remains as defined right after (36). Plugging all of this back in (89) gives us

The proof will be similar to the corresponding one from Subsection 2.1.2. We start by setting

Further, let $\nu^{(lip_{1})}$ and $\lambda^{(lip_{1})}$ be the solutions of the minimization in (94). Then, clearly

and let $\nu^{(lip_{2})}$ and $\lambda^{(lip_{2})}$ be the solutions of the minimization in (96). Then, clearly

Now assume that $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})\neq f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$ (if they are equal we are trivially done). Further let $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})<f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$ (the rest of the argument of course can trivially be flipped if $f_{lip}({\bf g}^{(1)},{\bf h}^{(1)})>f_{lip}({\bf g}^{(2)},{\bf h}^{(2)})$). We then have

We continue by following the line of arguments right after (LABEL:eq:probanalcont1). As stated there $P({\bf h}_{n+1}\sigma\geq-\epsilon_{1}^{({\bf h})}\sqrt{n})\geq 1-e^{-\epsilon_{2}^{({\bf h})}n}$ where $\epsilon_{1}^{({\bf h})}>0$ is an arbitrarily small constant and $\epsilon_{2}^{({\bf h})}$ is a constant dependent on $\epsilon_{1}^{({\bf h})}$ and $\sigma$ but independent on $n$. Set

One then has after combing (91) and Lemma 93

As stated after (20), (100) is conceptually enough to establish a “high probability” upper bound on $\zeta_{obj}$. What is left is to connect it with (84). Combining (100), (85), and (84) we then obtain

where we used the fact that $g$ is the standard normal and therefore $P(g-\epsilon_{3}^{(g)}\sqrt{n}\leq 0)\geq(1-e^{-\epsilon_{4}^{(g)}n})$ for an arbitrarily small $\epsilon_{3}^{(g)}>0$ and a constant $\epsilon_{4}^{(g)}$ dependent on $\epsilon_{3}^{(g)}$ but independent of $n$.

We are now in position to summarize results from this subsection in the following lemma which is essentially an “upper-bound” analogue to Lemma 5.

3 Matching upper and lower bounds

In this section we specialize the general bounds introduced above and show how they can match each other. We will divide presentation in three subsections. In the first of the subsections we will make a connection to the noiseless case and show how one can then remove the constraint from (45), (46), and (47). In the second subsection we will consider a ${\bf w}$ such that $|\|{\bf w}\|_{2}-\|\hat{{\bf w}}\|_{2}|\geq\epsilon_{{\bf w}_{up}}\|\hat{{\bf w}}\|_{2}$. We will then quantify how much the lower bound that can be computed for such a ${\bf w}$ through the framework presented in Section 2.1 deviates from the optimal one obtained for $\hat{{\bf w}}$. In the last subsection we will then show that there will be a ${\bf w}$ such that the upper bound computed through the framework presented in Section 2.2 will deviate less. That will in essence establish that upper and lower bounds computed in the previous sections indeed match. We will then draw conclusions as for the consequences which such a matching of the bounds leaves on a couple of LASSO parameters.

where $C_{\bf w}$ is an arbitrarily large constant and $\hat{\nu}$ and $\widehat{\lambda^{(2)}}$ are the solutions of

Now, to make the new observations easily comparable to the corresponding ones from we set

where $[|{\bf h}|_{(1)}^{(1)},|{\bf h}|_{(2)}^{(2)},\dots,|{\bf h}|_{(n-k)}^{(n-k)}]$ are magnitudes of $[{\bf h}_{1},{\bf h}_{2},\dots,{\bf h}_{n-k}]$ sorted in increasing order (possible ties in the sorting process are of course broken arbitrarily). Also we let ${\bf z}^{(2)}$ be such that ${\bf z}_{i}^{(2)}=-{\bf z}_{i}^{(1)},n-k+1\leq i\leq n$ and ${\bf z}_{i}^{(2)}={\bf z}_{i}^{(1)},1\leq i\leq n-k$. It is then relatively easy to see that the above optimization problem is equivalent to

Moreover, since $\lambda_{i}^{(2)}\geq 0,n-k+1\leq i\leq n$, in (105) one actually has that (111) implies that with overwhelming probability

3.2 Deviation from the lower-bound

One can then proceed further with solving the Lagrangian to obtain

Now, let as usual $\hat{\nu}$ and $\widehat{\lambda^{(2)}}$ be the solutions of (115). Let

For the simplicity let $|\|{\bf w}_{off}\|_{2}-\|\hat{{\bf w}}\|_{2}|=\epsilon_{{\bf w}_{up}}\|\hat{{\bf w}}\|_{2}$ (this restriction is clearly more conservative than $|\|{\bf w}_{off}\|_{2}-\|\hat{{\bf w}}\|_{2}|\geq\epsilon_{{\bf w}_{up}}\|\hat{{\bf w}}\|_{2}$). Now, we switch to expectations and ignore all $\epsilon$ except $\epsilon_{{\bf w}_{up}}$. Since every quantity that we will consider (see (55)) concentrates $\epsilon$’s in concentration inequalities can be made arbitrarily close to zero; moreover once $\epsilon_{{\bf w}_{up}}$ is fixed all other $\epsilon$’s can be made arbitrarily small compared to $\epsilon_{{\bf w}_{up}}$. Also, we will show derivation for ${\bf w}_{off}=(1+\epsilon_{{\bf w}_{up}})\|\hat{{\bf w}}\|_{2}$ (the derivation for the case ${\bf w}_{off}=(1-\epsilon_{{\bf w}_{up}})\|\hat{{\bf w}}\|_{2}$ is completely analogous).

Now, to facilitate writing we then set all $\epsilon$’s except $\epsilon_{{\bf w}_{up}}$ to zero. We then have

where $\doteq$ means that equality is not exact but for a fixed $\epsilon_{{\bf w}_{up}}$ can be made as close to it as needed. In a similar fashion we have

Before we proceed further we simplify the notation with the following change of variables.

Then a combination of (118), (120), and (121) gives

Now, assuming that $\epsilon_{{\bf w}_{up}}$ is small (and recognizing that $\xi_{E}\leq g_{E}\sigma$) from (122) we have

Combining (117), (122), and (123) we finally have

Now, roughly speaking, (124) shows that if $\|{\bf w}_{lasso}\|_{2}$ were to deviate from $\|\hat{{\bf w}}\|_{2}$ the optimal value of the objective in (6) would be higher than the lower bound derived in Section 2.1. We summarize these observations in the following lemma (essentially a deviating equivalent of Lemma 5 from Section 2.1).

Follows from the previous discussion, discussion from Section 2.3.1, and a combination of (114), (117), (124), arguments right after (114), and Lemma 5. ∎

3.3 Deviation of the upper bound

Rewriting (127) with a simple sign flipping turns out to be useful in what follows

The following lemma provides a powerful tool to deal with (128).

After solving the inner maximization over $d$ in (129) one has

Now we digress for a moment and consider the following optimization problem

Now, let us write the Lagrange dual of the optimization problem in (133). Let $d$ and $\gamma_{1}$ be Lagrangian variables such that

After solving the inner minimization over ${\bf q}_{1},{\bf q}_{2}$ in (138) we have

Since the first two terms in the objective function in (139) do not involve neither $\nu$ nor $\lambda^{(2)}$ one can then maximize their sum over $\gamma_{1}$ for any $d$. After that we finally have

On the other hand the optimization problem in (140) is the same as the one in (128) and therefore

Connecting (137), (141), and (142) one finally has

which is what is stated in (130). This concludes the proof. ∎

Let $\hat{d},\hat{\nu},\widehat{\lambda^{(2)}}$ be the solution of (127). Clearly, $\hat{d}=\|\hat{{\bf w}}\|_{2}=\sigma\frac{\|{\bf h}+\hat{\nu}{\bf z}^{(1)}-\widehat{\lambda^{(2)}}\|_{2}}{\sqrt{\|{\bf g}\|_{2}^{2}-\|{\bf h}+\hat{\nu}{\bf z}^{(1)}-\widehat{\lambda^{(2)}}\|_{2}^{2}}}$ and since all quantities concentrate $E\hat{d}=E\|\hat{{\bf w}}\|_{2}\doteq\sigma\frac{E\|{\bf h}+\hat{\nu}{\bf z}^{(1)}-\widehat{\lambda^{(2)}}\|_{2}}{\sqrt{E\|{\bf g}\|_{2}^{2}-E\|{\bf h}+\hat{\nu}{\bf z}^{(1)}-\widehat{\lambda^{(2)}}\|_{2}^{2}}}$. Now, set $C_{{\bf w}_{up}}=E\|\hat{{\bf w}}\|_{2}$ in (92). Then a combination of (92), (127), and Lemma 130 gives

4 Connecting all pieces

In this section we connect all of the above. We will summarize the results obtained so far in the following theorem.

Let $\hat{\nu}$ and $\widehat{\lambda^{(2)}}$ be the solution of (145). Set

where $\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(lasso)}$ is a constant dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

Follows from the above discussion and a combination of (42), Lemma 47, discussion in Section 2.3.1, and Lemmas 5, 14, and 130. ∎

and $\widehat{\lambda_{i}^{(2)}}\geq 0,n-k+1\leq i\leq n$, one has that

Furthermore, one then has for the norm of error vectors

Then the following generic equivalent to Theorem 1 can be established.

Assume the setup of Theorem 1. Consider the following optimization problem:

Let $\nu_{gen}$ and $\lambda^{(gen)}$ be the solution of (153). Set

where $\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(lasso)}$ and $\epsilon_{3}^{(lasso)}$ are constants dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

Follows from the above discussion, Theorem 1, and by noting that the optimization problems in (153) and (149) are equivalent. ∎

The following corollary then provides a quick way of computing the concentrating point of the “worst case” norm of the error vector.

Assume the setup of Theorems 1 and 2. Let $\alpha=\frac{m}{n}$ and $\beta_{w}=\frac{k}{n}$. Then

and $\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(lasso)}$ is a constant dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

Let $\bar{{\bf h}}$ and ${\bf z}^{(2)}$ be as in Section 2.3.1. Then

is equivalent to (LABEL:eq:genlasso7). Moreover

where $\alpha_{w}m\doteq E\xi_{ov}^{(gen)}(\sigma,{\bf g},{\bf h})^{2}$ is one of the main contributions of . The rest then trivially follows from (LABEL:eq:genlasso6). ∎

Using (157) and (149) one can then for any $\sigma$ and any pair $(\alpha,\beta_{w})$ (that is below fundamental characterization (110)) determine the value of the worst case $E\|{\bf w}_{lasso}\|_{2}$ as $\sigma\sqrt{\frac{\alpha_{w}}{\alpha-\alpha_{w}}}$. We present the obtained results in Figure 3. For several fixed values of worst case $E\|{\bf w}_{lasso}\|_{2}$ we determine curves of points $(\alpha,\beta_{w})$ for which these fixed values are achieved (of course for any $\alpha$ that is below a curve the value of the corresponding worst case $E\|{\bf w}_{lasso}\|_{2}$ is smaller). As can be seen from the plots the lower the norm-2 of the error vector the smaller the allowable region for pairs $(\alpha,\beta_{w})$.

The results of the above corollary match those obtained in through a state evolution/bilief propagation type of analysis. The above corollary relates to the LASSO from (6) whereas the results from are derived for somewhat different LASSO from (5). However, as mentioned earlier, in Section 4 we will establish a nice connection between the LASSO from (6) and one that is fairly similar to (5).

LASSO’s performance analysis framework – signed 𝐱𝐱{\bf x}

\zeta_{obj+} In this section we present the part of the framework that relates to finding a “high-probability” lower bound on $\zeta_{obj}^{+}$. As in the previous section we again assume that there is a (if necessary, arbitrarily large) constant $C_{\bf w}$ such that

where as earlier $A_{{\bf v}}=\begin{bmatrix}-A&{\bf v}\end{bmatrix}$ is an $m\times(n+1)$ random matrix with i.i.d. standard normal components. Let

Now, after applying Lemma 18 and following the procedure from the previous section one has

As in previous section we will essentially show that for certain $\zeta_{obj+}^{(l)}$ this probability is close to $1$ which will imply that we have a “high probability” lower bound on $\zeta_{obj+}$. Let

The Lagrange dual of the above problem then becomes

After a few further arrangements we finally have

One can then write the following dual problem of (171)

where we of course use the fact that the strict duality obviously holds. The inner minimization over ${\bf w}$ is now doable. Setting the derivatives with respect to ${\bf w}_{i}$ to zero one obtains

where ${\bf z}^{(1)}$ and $\lambda^{(2)}$ are as defined in the previous section. From (175) one then has

where ${\bf w}_{sol+}$ is of course the solution of the inner minimization over ${\bf w}$. As in the previous section, one should note that (178) and (179) are of course possible only if $\|{\bf g}\|_{2}+\gamma-\|{\bf h}+\nu{\bf z}^{(1)}-\lambda^{(2)}\|_{2}\geq 0$. (Also, as in the previous section if for $\nu$ and $\lambda^{(2)}$ that are optimal in (174) the condition is not met then for the corresponding ($\alpha,\beta$) the worst-case $\|{\bf w}\|_{2}$ is infinite with overwhelming probability). Plugging the value of ${\bf w}_{sol+}$ from (179) back in (174) gives

Now, the maximization over $\gamma$ can be done. After setting the derivative to zero one finds

where of course $\gamma_{opt+}$ would be the solution of (180) only if larger than or equal to zero. Alternatively of course $\gamma_{opt+}=0$. Now, based on these two scenarios we distinguish two different optimization problems:

The “overwhelming” optimization is the equivalent to (180) if for its optimal values $\widehat{\nu^{+}}$ and $\widehat{\lambda^{(2+)}}$ holds

We now summarize in the following lemma the results of this subsection.

Moreover, let $\widehat{{\bf w}^{+}}$ be the solution of (170). Then

The first part follows trivially. The second one follows from (179) by choosing the optimal $\widehat{\nu^{+}}$ and $\widehat{\lambda^{(2+)}}$ or alternatively $\widetilde{\nu^{+}}$ and $\widetilde{\lambda^{(2+)}}$. ∎

Moreover one then has that $\|{\bf h}+\widehat{\nu^{+}}{\bf z}^{(1)}-\widehat{\lambda^{(2+)}}\|_{2}$ and $\|{\bf h}+\widetilde{\nu^{+}}{\bf z}^{(1)}-\widetilde{\lambda^{(2+)}}\|_{2}$ concentrate as well which automatically implies that $\widehat{{\bf w}^{+}}$ also concentrates. More formally, one then has analogues to (189)

where as usual $\epsilon_{1}^{(norm)}>0$, $\epsilon_{2}^{(norm)}>0$, and $\epsilon_{1}^{({\bf w})}>0$ are arbitrarily small constants and $\epsilon_{3}^{(norm)}$, $\epsilon_{4}^{(norm)}$, and $\epsilon_{2}^{({\bf w})}$ are constant dependent on $\epsilon_{1}^{(norm)}>0$, $\epsilon_{2}^{(norm)}>0$, and $\epsilon_{1}^{({\bf w})}>0$, respectively, but independent of $n$. After repeating every step between (55) and (64) one arrives to the following analogue to Lemma 5.

where $A_{\bf v}$ is as defined right after (14). If we can show that with overwhelming probability the objective value of the above optimization problem is negative then $r_{+}$ will be a valid “high probability” upper-bound on $\zeta_{obj+}$. Moreover, it will be achieved by a ${\bf w}$ for which it will hold that $\|{\bf w}\|_{2}\leq C_{{\bf w}_{up+}}$.

First let us rewrite the objective value of the above optimization problem in a slightly more convenient form

Now, we proceed in a fashion similar to the one from Subsection 3.1.1. We first do a slight modification of the first constraint from (194) in the following way

The Lagrange dual of the above problem then becomes

where $\nu^{(1)}$ and $\lambda^{(2)}$ are vectors of Lagrange variables as in previous sections. After rearranging terms we further have

Finally we can write a dual problem to (195)

where we of course use the fact that the strict duality obviously holds. Now, after repeating all the steps from (75) to (84) (wherever we had $2\lambda^{(2)}$ we would now have $\lambda^{(2)}$ and there will be no upper bound on components of $\lambda^{(2)}$ in the corresponding optimization problems) one obtains and analogue to (84)

Any $r_{+}$ such that $\lim_{n\rightarrow}P(f_{obj+}^{(up)}\geq 0)=1$ is then a valid “high-probability” upper bound. Set

After further repeating all the steps between (84) and Lemma 14 (the only difference is that $\lambda_{i}^{(2)}\in\Lambda^{(2+)}$ in the “signed” scenario) one then has the following “signed” analogue to Lemma 14 (which in essence gives a way of finding an $r_{+}$ such that $\lim_{n\rightarrow}P(f_{obj+}^{(up)}\geq 0)=1$).

3 Matching upper and lower bounds

In this section we specialize the general bounds introduced above and show how they match. We will again divide presentation in three subsections. In the first of the subsections we will make a connection to the noiseless “signed” case and show how one can then remove the constraint from (186), (187), and (188). In the second subsection we will consider a ${\bf w}$ such that $|\|{\bf w}\|_{2}-\|\widehat{{\bf w}^{+}}\|_{2}|\geq\epsilon_{{\bf w}_{up}}\|\widehat{{\bf w}^{+}}\|_{2}$. We will then quantify how much the lower bound that can be computed for such a ${\bf w}$ through the framework presented in Section 3.1 deviates from the optimal one obtained for $\widehat{{\bf w}^{+}}$. In the last subsection we will then show that there will be a ${\bf w}$ such that the upper bound computed through the framework presented in Section 3.2 will deviate less. That will in essence establish that upper and lower bounds computed in the previous sections indeed match.

where $C_{\bf w}$ is an arbitrarily large constant and $\widehat{\nu^{+}}$ and $\widehat{\lambda^{(2+)}}$ are the solutions of

To make the new observations easily comparable to the corresponding ones from we set

where $[{\bf h}_{(1)}^{(1)},{\bf h}_{(2)}^{(2)},\dots,{\bf h}_{(n-k)^{(n-k)}}]$ are $[{\bf h}_{1},{\bf h}_{2},\dots,{\bf h}_{n-k}]$ sorted in increasing order (possible ties in the sorting process are of course broken arbitrarily). Also we let ${\bf z}^{(2)}$ be as in the previous section, i.e. let it be such that ${\bf z}_{i}^{(2)}=-{\bf z}_{i}^{(1)},n-k+1\leq i\leq n$ and ${\bf z}_{i}^{(2)}={\bf z}_{i}^{(1)},1\leq i\leq n-k$. It is then relatively easy to see that the above optimization problem is equivalent to

Then, as we showed in and , the inequality

Moreover, since $\lambda_{i}^{(2)}\geq 0,n-k+1\leq i\leq n$, in (206) one actually has that (213) implies that with overwhelming probability

3.2 Deviation from the lower-bound

One can then write a “signed” analogue to (114)

After repeating all the arguments between (114) and Lemma 9 one obtains the following analogue to Lemma 9.

Follows from the discussion in Section 2.3.2. ∎

3.3 Deviation of the upper bound

In this section we establish that $\|{\bf w}_{lasso+}\|_{2}$ can not deviate from $\|\widehat{{\bf w}^{+}}\|_{2}$ as much as it was assumed in the previous section which is conceptually enough to make the bounds from Sections 3.1 and 3.2 match. All arguments from Section 2.3.3 can be repeated again. The only difference will be that in all optimization problems from Section 2.3.3 one will now have no upper bound on $\lambda_{i}^{(2)},1\leq i\leq n$ (this essentially amounts to using set $\Lambda^{(2+)}$ instead of set $\Lambda^{(2)}$). One then has a “signed” analogue to (144)

4 Connecting all pieces

In this section we connect all of the above. The following theorem essentially does so.

Let $\widehat{\nu^{+}}$ and $\widehat{\lambda^{(2+)}}$ be the solution of (219). Set

where $\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(lasso)}$ is a constant dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

In this section we show how the results presented in the above theorem can be adapted to the so-called “worst-case” scenario or as we refer to it “generic performance” scenario. Repeating the line of arguments from Section 2.4.1 one can establish the following generic equivalent to Theorem 3.

Assume the setup of Theorem 3. Consider the following optimization problem:

Let $\nu_{gen+}$ and $\lambda^{(gen+)}$ be the solution of (223). Set

where $\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant and $\epsilon_{2}^{(lasso)}$ and $\epsilon_{3}^{(lasso)}$ are constants dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

Follows by the use of the same arguments that were used to establish Theorem 3. ∎

The following corollary then provides a quick way of computing the concentrating point of the “worst case” norm of the error vector.

Assume the setup of Theorems 3 and 4. Let $\alpha=\frac{m}{n}$ and $\beta_{w}^{+}=\frac{k}{n}$. Then

where $\alpha_{w}^{+}<\alpha$ is such that

$\epsilon_{1}^{(lasso)}>0$ is an arbitrarily small constant, and $\epsilon_{2}^{(lasso)}$ and $\epsilon_{2}^{(lasso)}$ are constants dependent on $\epsilon_{1}^{(lasso)}$ and $\sigma$ but independent of $n$.

Follows by the use of the same arguments that were used to establish Corollary 1 and a recognition that the fundamental characterization of interest in the “signed” case is the one given in (212). ∎

Based on the above corollary one can then for any $\sigma$ and any pair $(\alpha,\beta_{w}^{+})$ (that is below fundamental characterization (227) or alternatively (212)) determine the value of the worst case $E\|{\bf w}_{lasso+}\|_{2}$ as $\sigma\sqrt{\frac{\alpha_{w}^{+}}{\alpha-\alpha_{w}^{+}}}$. We present the obtained results in Figure 4. For several fixed values of the worst case $E\|{\bf w}_{lasso+}\|_{2}$ we determine curves of points $(\alpha,\beta_{w}^{+})$ for which these fixed values are achieved (of course for any $\alpha$ that is below a curve the value of the corresponding worst case $E\|{\bf w}_{lasso+}\|_{2}$ is smaller). As in the previous section, the lower the norm-2 of the error vector the smaller the allowable region for pairs $(\alpha,\beta_{w}^{+})$. Also as it was the case in the previous section, the results of the above corollary match those obtained in through a state evolution/bilief propagation type of analysis for the “signed” version of the LASSO from (5) (signed version of the LASSO from (5) as expected assumes just simple adding of the positivity constraints on the components of ${\bf x}$).

Connecting LASSO’s from (6) and (5)

In this section we establish a connection between the LASSO algorithm from (6) that we analyzed in Section 2 and the more well known form of LASSO from (5). Instead of well-known (5) we will consider its a slight modification

Now, let $\lambda_{lasso}$ in (228) be such that $\lambda_{lasso}=E\hat{\nu}$ where $\hat{\nu}$ is the solution of (42). Then (228) becomes

This could be rewritten in a way analogous to (14) as

where $A_{{\bf v}}$ is as in (14). One can then repeat all arguments from the beginning of Section 2.1 (essentially those before Section 2.1.1) to arrive at the following analogue of (23)

Now, one should note that $E\hat{\nu}$ in the above optimization is chosen as the “optimal” (it is actually the concentrating point of the optimal one; to make this really precise one would need to go through all the probabilistic arguments of Section 2 and plus some more) $\nu$ in the Lagrange dual of (23). One then has that arguments from Section 2.1 (essentially an appropriate repetition of those that follow (23)) will produce the lower bound on the objective of (230) that is with overwhelming probability arbitrarily close to the one derived in Lemma 5. The arguments from Section 2.2 related to the upper bound can be trivially repeated as well since the negativity of the objective in (67) implies that $r$ is also an upper bound on the optimal value of the objective in (230). The matching arguments from Section 2.3 then follow as well. Now if one let ${\bf w}_{conn}$ be the solution of (231), then with overwhelming probability $\|{\bf w}_{conn}\|_{2}$ concentrates around $E\|\hat{{\bf w}}\|_{2}$, where $\hat{{\bf w}}$ is as defined in Theorem 1.

For the signed case the arguments are the same, only instead of $E\hat{\nu}$ in (229), (230), and (231) one should use $E\widehat{\nu^{+}}$ where $\widehat{\nu^{+}}$ is the solution of (183). Also, as it is probably obvious, this time $\|{\bf w}_{conn}\|_{2}$ concentrates around $E\|\widehat{{\bf w}^{+}}\|_{2}$ where $\widehat{{\bf w}^{+}}$ is as defined in Theorem 3.

A relation between a LASSO and an SOCP

As we hinted above what we presented here is only a characterization of a particular performance measure of an SOCP algorithm (the same is of course true for the LASSO algorithms). How adequate is such a performance measure is whole another story that we will explore in more detail elsewhere.

Numerical results

In this subsection we will present numerical results that relate to the theoretical ones created in Sections 2 and 4. We will consider two groups of $(\alpha,\beta_{w})$ regimes, one that we will refer to as the low $(\alpha,\beta_{w})$ regime and the other that we will refer to as the high $(\alpha,\beta_{w})$ regime.

2) Low $(\alpha,\beta_{w})$ regime — $\rho=\frac{E\|{\bf w}_{lasso}\|_{2}}{\sigma}=2$

2) High $(\alpha,\beta_{w})$ regime — $\rho=\frac{E\|{\bf w}_{lasso}\|_{2}}{\sigma}=3$

2 Numerical results related to signed 𝐱𝐱{\bf x}

In this subsection we will present numerical results that relate to the theoretical ones created in Sections 3 and 4. We will again consider two groups of $(\alpha,\beta_{w}^{+})$ regimes, one that we will refer to as the low $(\alpha,\beta_{w}^{+})$ regime and the other that we will refer to as the high $(\alpha,\beta_{w}^{+})$ regime.

2) Low $(\alpha,\beta_{w}^{+})$ regime — $\rho=\frac{E\|{\bf w}_{lasso+}\|_{2}}{\sigma}=2$

2) High $(\alpha,\beta_{w}^{+})$ regime — $\rho=\frac{E\|{\bf w}_{lasso+}\|_{2}}{\sigma}=3$

As in the previous subsection we also ran a carefully designed set of experiments intended to show a specific behavior of the LASSO’s from (160) and (229) in what we will refer to as the high $(\alpha,\beta_{w}^{+})$ regime. Following further the methodology of the previous subsection for $\alpha\in\{0.3,0.5,0.7\}$ we determined three values of $\beta_{w}^{+}$ from the contour LASSO line that corresponds to $\rho=3$ in the figure given in Section 3. We then again ran (160) and (229) (when running (229) we of course again added positivity constraints and we again used theoretical value for $E\widehat{\nu^{+}}$). When $\alpha=0.7$ we set $n=1500$ while for the other two values of $\alpha$ we set $n=2000$. Obtained results are presented in Table 4. The theoretical values for all quantities of interest are again given in parallel as bolded numbers. We once again observe a solid agreement between the theoretical predictions and the results obtained through numerical experiments.

Discussion

While many quantities of interest in LASSO recovery can be computed through the mechanism presented here, to demonstrate its power we in this introductory paper focused only on, what we called, LASSO’s generic performance. We essentially established the precise values of the “worst-case” norm-2 of the error vector. On the other hand, using the framework one can create a massive set of results for the LASSO’s non-generic or as we will refer to it problem dependent performance. However, this goes significantly over the scope of an introductory paper. We will dissect problems from this direction into tiny details in one of the forthcoming papers. Also, the existence of an SOCP type of the recovery algorithm that achieves the same norm-2 of the error vector as the LASSO does followed as a by-product of our analysis.

As for the applications, further developments are pretty much unlimited. Literally every problem that we were able to solve in the so-called noiseless case (and there was hardly any that we were not) through the mechanisms from and can now be handled in the noisy case as well. For example, quantifying performance of LASSO or SOCP optimization problems in solving “noisy” systems with special structure of the solution vector (block-sparse, binary, box-constrained, low-rank matrix, partially known locations of nonzero components, just to name a few), “noisy” systems with noisy (or approximately sparse)) solution vectors can then easily be handled to an ultimate precision. In a series of forthcoming papers we will present some of these applications.

References