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:

  $$ \min_{x\geq 0} \quad \mu || Ax - 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:

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

This approach however, 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.

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.