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.