# Solving LASSO (Basis Pursuit Denoising Form) with LARS

I'm now working on using LARS (Least Angle Regression) algorithm to solve a LASSO problem in Basis Pursuit Denoising form like:

\begin{align*} \quad && \arg \min_{\beta}{\left\| y - X\beta \right\|}_{2}^{2} + \lambda {\left\| \beta \right\|}_{1} && (1) \end{align*}

I have done many search jobs on the web, what confused me is LARS is more like an algorithm to solve problems in this form:

\begin{align*} \quad & \arg \min_{\beta} {\left\| y - X\beta \right\|}_{2}^{2} && \text{subject to.} && {\left\| \beta\right\|}_{1} \leq t && (2) \end{align*}

I know these two forms is equal to each other in theory and LARS can solve problem(1) for all 0<λ≤∞. But I want know how to use LARS to solve problem(1) in practice, which means how can I write a function like:

function lars(X, y, lambda){
...
return beta;
}

• I'm assuming your $||\cdot||$ denotes a two-norm and your $|\cdot|$ denotes a one-norm? In this case, as far as I know, the following is true: for every $\lambda$ in (1) there exists a $t$ in (2) such that (1) and (2) give the same solution. However, I wouldn't know of any explicit way to convert one into the other and I would claim this is not easy. But I'm curious if other folks around here know more. Btw: might also be a fitting question for Math.Stackexchange (I mean how to find $t$ given $\lambda$). Apr 1 '20 at 6:30
• Please use LaTeX for the math expressions. See MathJax Basic Tutorial and Quick Reference.
– Royi
Apr 1 '20 at 6:31
• Related dsp.stackexchange.com/questions/21730, dsp.stackexchange.com/questions/21734, stats.stackexchange.com/questions/291962. Pay attention that the connection between $\lambda$ and $\epsilon$ is data dependent. See my linked answers.
– Royi
Apr 1 '20 at 6:34
• Yes, ||⋅|| denotes a L2-norm and |⋅| denotes a L1-norm. @Florian Apr 1 '20 at 6:47
• I'll try to edit it use LaTeX. @Royi Apr 1 '20 at 6:49

## 1 Answer

There are 2 forms of the Basis Pursuit problem:

\begin{align*} \text{The \lambda Form:} & \quad && \arg \min_{x} &&\frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \\ \text{The \epsilon Form:} && \quad & \arg \min_{x} && {\left\| x \right\|}_{1} \\ && \quad & \text{subject to} && \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \leq \epsilon \end{align*}

Real world model is:

$$A x = y$$

Where $$x$$ is a sparse vector.
Yet, in reality we don't have measurements of $$y$$ but $$b = y + v$$ where $$v$$ is a vector with the properties of our measurement method.

Hence we allow the model not to have strict equality which implies:

$${\left\| A x - b \right\|}_{2}^{2} \leq \epsilon = {\left\| v \right\|}_{2}^{2}$$

Now, the different models are equivalent as for any $$\epsilon$$ there is a $$\lambda$$ (Which depends on $$A$$ and $$b$$ unfortunately) which the models ( (1) and (2) ) are equivalent.

For instance I created simple simulation on for that simulation:

The full code is available on my StackExchange Cross Validated Q291962 GitHub Repository.

Since you linked to the paper you're reading - Sparse Geometric Representation Through Local Shape Probing the problem solved there is the $$\lambda$$ form.
Since it is a strict Convex Problem there is a single solution. LARS isn't considered a very efficient or fast method to solve the problem, hence I recommend using a different solution.

I have a project with many solvers of the $${L}_{1}$$ Regularized Least Squares. I suggest you just take the Proximal Gradient Method - SolveLsL1Prox.m or the Accelerated Proximal Gradient Descent Method - SolveLsL1ProxAccel.m.

So you can just pick any of those MATLAB codes and solve the problem.

• Thanks for your answer. I have checked your github repo, but I didn't find LARS code which is my primary goal. Apr 1 '20 at 7:06
• The idea is you'll have to do what I did in the code. For any solution of LARS to check the value of the objective function in $\lambda$ form. By the way, it makes no sense to solve this in that way.
– Royi
Apr 1 '20 at 8:01
• Thanks again for your patient, but I'm still confused. I ask this question because there is a paper use LARS to solve a problem like (1) in my post. I want to implement that paper, so I have to figure it out. Apr 1 '20 at 8:18
• Give us a link to the paper. Again, you can do it, but you will have to analyze each solution of the LARS.
– Royi
Apr 1 '20 at 8:31
• the paper link : perso.liris.cnrs.fr/julie.digne/articles/lpf.pdf , "lars" is mentioned in section 3.3 Apr 1 '20 at 8:45