Derivation of the Iterative Reweighted Least Squares Solution for $ {L}_{1} $ Regularized Least Squares Problem I'm trying to fitting a line with IRLS with L1 norm, but I'm struggling to understand why my idea is wrong.
1 - init the weights $w$
2 - fit with simple LS and obtain a starting model $\beta_0$
3 - at each iteration t then until convergence do:


*

*compute the residuals $e = |y - x\beta_0|$

*update the weights $w = \dfrac{1}{e}$ ? (Not sure about this)

*build the matrix $W = diag(w)$ ? (Not sure about this)

*update the model $(x'Wx)x'Wy$
Can someone give an explanation of what am I doing wrong, cause I'm not sure if I update the weights in the right way.
 A: The IRLS for the LASSO / Least Squares with $ {L}_{1} $ Regularization problem is as following:
$$ \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} = \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda {x}^{T} W {x} $$
Where $ W $ is a diagonal matrix - $ {W}_{i, i} = \frac{1}{ \left| {x}_{i} \right| } $.
This comes from $ \left\| x \right\|_{1} = \sum_{i} \left| {x}_{i} \right| = \sum_{i} \frac{ {x}_{i}^{2} } { \left| {x}_{i} \right| } $.
Now, the above is just Tikhonov Regularization.
Yet, since $ W $ depends on $ x $ one must solve it iteratively (Also this cancels the 2 factor in Tikhonov Regularization, As the derivative of $ {x}^{T} W x $ with regard to $ x $ while holding $ x $ as constant is $ \operatorname{diag} \left( \operatorname{sign} \left( x \right) \right) $ which equals to $ W x $):
$$ {x}^{k + 1} = \left( {A}^{T} A + \lambda {W}^{k} \right)^{-1} {A}^{T} b $$
Where $ {W}_{i, i}^{K} = \frac{1}{ \left| {x}^{k}_{i} \right| } $.
Initialization can be by $ W = I $.
Pay attention that you better use ADMM or Coordinate Descent.
