I want to try and use Gauss-Newton in order to estimate a solution to the regression problem with normalizing factor $$\min_{x \in \mathbb{R}^n}: \|y - Ax\|_2^2 + \lambda\|x\|_1.$$

To do this, I have to rewrite this minimization as a non-linear least squares $\min_{x \in \mathbb{R}^n} \|r(x)\|^2$ where $r: \mathbb{R}^n \to \mathbb{R}^m$. I'm having some trouble defining $r_i$ such that this works out.

I want $r_i$ such that $r_i^2(x) = (y_i - a_i^Tx)^2 + \frac{\lambda}{m}\|x\|_1$, but finding a way to get the square to equal the $\ell_1$ norm of $x$ is proving difficult.

I'm considering rewriting $$ \|x\|_1 = \|B(x)x\|_2$$ where $B(x)$ is a diagonal matrix with $B(x)_{ii} = \frac{1}{\sqrt{x_i}}$ so the problem becomes

$$\min_{x \in \mathbb{R}^n} \|y - Ax\|_2^2 + \lambda\|B(x)x\|_2^2$$ which can be combined using weighted least squares to get a fairly ugly expression for $r_i$. Anyone have a good sense of whether this will be easy to apply G-N to?

  • $\begingroup$ 1) you want $B(x)x$ equals $\sqrt{|x|}$ component wise. Otherwise, the square root will become complex. 2) G-N might have a hard time to flip the sign of $x_i$, as $\sqrt{|x_i|}$ is not differentiable at $0$. So you need to guess the sign of each component of $x$ right initially. Just try it. 3) you might try some constraint optimization techniques instead. $\endgroup$ – user251257 Jul 26 '15 at 23:38
  • $\begingroup$ @shuckles: Why must you do Gauss-Newton ? These days, nobody solves such problems using Gauss-Newton. Use ISTA (Iterative Shrinkage Thresholding Algorithm or FISTA (Fast ISTA) instead. These algorithms can be written in less than 4 lines of (native) code and enjoy rigorous convergence theories. In particular, they have $\mathcal{O}(1/\epsilon)$ and $\mathcal{O}(1/\sqrt{\epsilon})$ global convergence rates resp. Lemme know if you need more light on this. $\endgroup$ – dohmatob Jul 27 '15 at 7:26
  • $\begingroup$ A reference would be nice. G-N was just out of curiosity and my available knowledge of approximation tools. $\endgroup$ – user83387 Jul 27 '15 at 7:27
  • $\begingroup$ You can start here google.fr/…. $\endgroup$ – dohmatob Jul 27 '15 at 7:30
  • 1
    $\begingroup$ Also checkout my answers to related questions: math.stackexchange.com/a/1311138/168758, etc. $\endgroup$ – dohmatob Jul 27 '15 at 7:32

Your Answer

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