I need to solve the following 4th order nonnegative LASSO problem: $$ \min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1 $$ where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e.g., $A \in \mathbb{R}^{100\times100}$).

This problem is non-convex and I worry about the convergence and stucking at saddle points.

My efforts

Split the original problem as following: $$ \begin{aligned} & \min_{x \geq 0, \, y} & & || |y|^2 - b ||^2 + \lambda ||x||_1 \\ & \,\,\,\,\text{s.t.} & & y = Ax \end{aligned} $$ Then the optimization can be done using primal-dual algorithms (e.g. Chambolle-Pock's), resulting two updating sub-steps:

  • $x$-update is a nonnegative LASSO problem which is solvable (given $y$ estimation $\hat{y}$):

    $$ \min_{x\geq 0} \quad \mu || Ax - \hat{y} ||^2 + \lambda ||x||_1 $$

  • $y$-update is a 4th order element-wise problem, and can be solved via exhaustive search or Newton's method, yet the convergence is unknown to me (given $x$ estimation $\hat{x}$):

    $$ \min_{y} \quad || |y|^2 - b ||^2 + \mu || y - A\hat{x} ||^2 $$


  • My implementation does not converge; as well as for the proximal gradient descent. From my numerical experiments it seems the initial point plays a very, very important role.

  • Therefore, this approach it is unclear if we can end up with a point sufficiently closes to the optimal.


I wonder if there are other approaches for this problem. Provable efficient methods are preferrable.

  • $\begingroup$ Do you have an example with values for $b$, $A$ and $\lambda$? $\endgroup$ – nicoguaro Jun 8 '19 at 16:40
  • $\begingroup$ @nicoguaro If I understand it correctly you are asking for a specific numerical example. Sorry I do not have one. (In fact for my practical engineering scenes only $A$ is controllable) For my case $A$ could be a circular matrix (i.e. diagonalizable in Fourier domain). For now $A$ can be assumed as a Laplacian matrix with stencil $-1, 2, -1$. And there’s no specific requirements for other variables. $\endgroup$ – WDC Jun 8 '19 at 16:46
  • $\begingroup$ Yes, that's what I meant. If you don't have those parameters how can you say that you don't have convergence? $\endgroup$ – nicoguaro Jun 8 '19 at 16:49
  • $\begingroup$ @nicoguaro well i thought math was enough. I could have provided one of my real data here if you want it. (This question will be edited later) $\endgroup$ – WDC Jun 8 '19 at 16:58

Your Answer

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

Browse other questions tagged or ask your own question.