# How are Least Angle Regresson (Efron 2004) and Least Squares Approximation for United Lasso (Wang, Leng 2007) related?

Least Squares Approximation (LSA) for Unifed Lasso (Wang, Leng 2007) mentions Least Angle Regression (LAR) several times. Here's a direct link to the paper.

Specifically, in Section 4 they say:

All studies were conducted in R with the lars package (Efron et al. 2004). This package (and many others used here) can be downloaded at http://cran.r-project.org/. The LSA method uses $\widetilde{\beta}$ and $\widehat{\Sigma}$ as standard inputs. The computational load consists of one single unpenalized full model fitting and one additional LARS processing; therefore, the extra computational cost is minimal.

I'm having trouble seeing the connection between LAR and LSA. From my understanding, LSA tells us that any LASSO style problem with a loss function $\mathcal{L}_n$ can be approximated by $(\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}) + \sum_{j=1}^{d} \lambda_j |\beta_j|$, where $\widetilde{\beta}$ is the OLS estimate of $\beta$.

How does LSA give us the approximate LASSO solution to the approximation above?

The Least Squares Approximation (LSA) method justifies the approximation $\mathcal{L_n(\beta)} \approx (\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}).$ This is used to approximate a complex objective function in a LASSO problem by one that is simpler: $$\mathcal{L}_n(\beta) + \sum_{j=1}^{d} \lambda_j |\beta_j| \approx (\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}) + \sum_{j=1}^{d} \lambda_j |\beta_j|.$$ The approximation is illustrated in Section 2.2 of the paper by assuming some smoothness in $\mathcal{L_n}$ and using a Taylor series approximation, although the authors assert that the method does not depend on this assumption. The right-hand side is the objective function of an $L_1$-penalized least squares problem that can be solved using (a simple modification of) the LARS algorithm. So, LSA does not provide the solution. Rather, LSA is a method for approximating the LASSO problem, and LARS is used to find the solution to that simpler problem.
• I'm not sure either; I have not implemented this method before. One could use a Cholesky decomposition to write $\hat{\Sigma^{-1}} = M^TM$; then the least squares part can be written as \begin{align} (\beta - \widetilde{\beta})^T M^TM (\beta - \widetilde{\beta}) & = [M(\beta - \widetilde{\beta})]^T[M (\beta - \widetilde{\beta})] \newline & = (M\widetilde{\beta} - M\beta)^T(M\widetilde{\beta} - M\beta) \newline & = (\widetilde{Y} - M\beta)^T(\widetilde{Y} - M\beta), \end{align} where $\widetilde{Y} = M\widetilde{\beta}$. – Breaking Waves May 25 '17 at 21:28
• This would suggest using the LARS algorithm (modified to produce the LASSO path) with response equal to $M$ times the OLS estimate, and predictor equal to $M$. Chenlei Leng, one of the authors, has as an implementation in R along with some examples on his website (see the last item under Software), so you could try using that as well. – Breaking Waves May 25 '17 at 21:28