6
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.