# 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.

• Your question is ambiguous - the title of your question suggests you would like to fit a least squares problem with an L1 regularization term using IRLS (which you can do as in the answer below) but your code suggests instead that you would like to fit a regression line using L1 loss, following en.wikipedia.org/wiki/Iteratively_reweighted_least_squares. Which of those two would you like to do? And why do you think that your L1 regression is not working? – Tom Wenseleers Sep 26 at 15:16

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.

• The OP uses L1 (absolute) loss, as used in robust regression, not the L2 loss mentioned in your answer. – sebp Aug 7 '18 at 12:43
• @sebp, You -1 without a reason. The method of IRLS (Iterative Reweighted Least squares) is about solving the ${L}_{1}$ problem by adaptive weight to imitate it. I solved for ${L}_{1}$ and this is the IRLS solution. Pay attention to how ${W}^{k}$ is defined to imitate ${L}_{1}$ Norm. – Royi Aug 7 '18 at 13:20
• I can somehow see what you are trying to say in your answer, but I find it confusing. Your initial objective is squared error with a LASSO penalty instead of least absolute deviation. After transformation to a weighted least squares problem the weights $W_{i,i}$ in your answer only contain the unknown $x_i$, whereas it should be the residuals. – sebp Aug 8 '18 at 18:26
• @sebp, I didn't invent anything here. Your -1 has no justification. This is the correct derivation of the IRLS for the problem I stated above. – Royi Aug 8 '18 at 18:33
• Could those who -1 please comment why? This is a correct derivation of the IRLS to the problem stated above. – Royi Jun 11 at 18:34