2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tom Wenseleers Sep 26 at 15:16
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The OP uses L1 (absolute) loss, as used in robust regression, not the L2 loss mentioned in your answer. $\endgroup$ – sebp Aug 7 '18 at 12:43
  • $\begingroup$ @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. $\endgroup$ – Royi Aug 7 '18 at 13:20
  • 1
    $\begingroup$ 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. $\endgroup$ – sebp Aug 8 '18 at 18:26
  • $\begingroup$ @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. $\endgroup$ – Royi Aug 8 '18 at 18:33
  • $\begingroup$ Could those who -1 please comment why? This is a correct derivation of the IRLS to the problem stated above. $\endgroup$ – Royi Jun 11 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.