# How to solve a 4th order nonnegative LASSO problem?

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$$

Issues

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

Question

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

• Do you have an example with values for $b$, $A$ and $\lambda$? – nicoguaro Jun 8 '19 at 16:40
• @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. – WDC Jun 8 '19 at 16:46
• Yes, that's what I meant. If you don't have those parameters how can you say that you don't have convergence? – nicoguaro Jun 8 '19 at 16:49
• @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) – WDC Jun 8 '19 at 16:58