Solving LASSO (Basis Pursuit Denoising Form) with LARS

Question

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;
}

Answer 1

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.