# 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

\begin{align} \Phi(x) = \lvert|(Ax)\odot(Ax)-b |\rvert^2+\lambda\lvert|x|\rvert_1 \end{align}
\begin{align} x_{k+1} = \mathcal{P}\left(x_k-\alpha A^T\left(\left((Ax_k)\odot(Ax_k)-b\right)\odot(Ax_k)\right)\right) \end{align}
With $$\mathcal{P}$$ being the projection onto a scaled L1 ball and $$\alpha$$ being the step size. The important part to point out is the $$\odot (Ax_k)$$ at the end of the expression. If $$x_k$$ is shrinked, it reduces the gradient strength in the region/near where it was shrinked. So if $$x_k$$ becomes sparse, there may be region where the gradient becomes extremely small. Then you might be stuck and can't converge to the global minimum anymore.
That can also make a problem if the kernel has certain properties. E.g suppose the input $$x$$ has a region that is more or less constant. This region would yield a very low $$Ax$$ if the kernel for a convolution is antisymmetric. As a consequence, the gradient would also be very small, even though a large chunk of $$x$$ could be located there.