1
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ 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$). $\endgroup$ – Florian Apr 1 at 6:30
  • $\begingroup$ Please use LaTeX for the math expressions. See MathJax Basic Tutorial and Quick Reference. $\endgroup$ – Royi Apr 1 at 6:31
  • $\begingroup$ 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. $\endgroup$ – Royi Apr 1 at 6:34
  • $\begingroup$ Yes, ||⋅|| denotes a L2-norm and |⋅| denotes a L1-norm. @Florian $\endgroup$ – Leeleelee Apr 1 at 6:47
  • $\begingroup$ I'll try to edit it use LaTeX. @Royi $\endgroup$ – Leeleelee Apr 1 at 6:49
0
$\begingroup$

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} \\ & \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:

enter image description here

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. I have checked your github repo, but I didn't find LARS code which is my primary goal. $\endgroup$ – Leeleelee Apr 1 at 7:06
  • $\begingroup$ 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. $\endgroup$ – Royi Apr 1 at 8:01
  • $\begingroup$ 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. $\endgroup$ – Leeleelee Apr 1 at 8:18
  • $\begingroup$ Give us a link to the paper. Again, you can do it, but you will have to analyze each solution of the LARS. $\endgroup$ – Royi Apr 1 at 8:31
  • $\begingroup$ the paper link : perso.liris.cnrs.fr/julie.digne/articles/lpf.pdf , "lars" is mentioned in section 3.3 $\endgroup$ – Leeleelee Apr 1 at 8:45

Your Answer

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

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