Least angle regression

A piecewise linear regression-path algorithm which starts at zero, activates a predictor with maximal absolute residual score, and moves in a direction that decreases all active absolute scores equally until another predictor ties them. With $G=X^{\mathsf{T}}X/n$ and active correlation signs $s_A$, the coefficient direction is $G_{AA}^{-1}{s}_A$. Ordinary LAR does not drop a predictor when its coefficient crosses zero; sign compatibility of LAR and Lasso characterizes when its path also obeys the Lasso KKT conditions.

With signed active covariate columns $X_A^s=(s_j{x}_j{)}_{j\in A}$ and their positive-definite Gram matrix $G_A=(X_A^s{)}^T{X}_A^s$, the displayed direction has unit norm and $(X_A^s{)}^{T}u=\alpha 1$. Thus it makes equal angles with unit-length signed active covariates, and movement along it reduces their signed residual correlations at the common rate $\alpha$. The regression coefficient direction is $d_A=\mathrm{diag}(s_A)w$, with inactive components zero.

If every nonzero active coefficient has the sign of its residual score along the least angle regression path, the LAR active correlation invariant and inactive bounds give the Karush-Kuhn-Tucker conditions for the Lasso. A unique Lasso solution then equals the LAR path. Zero coefficients use a subgradient interval; literal sign equality with sign(0)=0 is not appropriate for a newly entering coefficient at a positive knot.

Each least angle regression segment starts with all active scores at magnitude $t$. Moving with direction $d_A=G_{AA}^{-1}{s}_A$ changes the score vector to $t{s}_A-(t-\lambda )G_{AA}{d}_A=\lambda s_A$. The first-hit rule bounds every inactive score in magnitude by $\lambda$. This is the key Lasso optimality link.

On a segment starting at residual-score level $t$, an inactive score evolves as $c_j-h{a}_j$ while the active level is $t-h$. Solving $c_j-h{a}_j=\pm (t-h)$ gives distances $(t-c_j)/(1-a_j)$ and $(t+c_j)/(1+a_j)$. The smallest positive admissible distance determines the next entry; reaching level zero ends the algorithm.