How to solve a 4th order nonnegative LASSO problem?

Question

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.

Answer 1

I guess a problem with this approach is that it also "sparsifies" the gradient. If you look at the objective function:

\begin{align} \Phi(x) = \lvert|(Ax)\odot(Ax)-b |\rvert^2+\lambda\lvert|x|\rvert_1 \end{align}

If one uses a proximal gradient method, we have

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