Title: Non-Convex Rank/Sparsity Regularization and Local Minima,
Abstract: This paper considers the problem of recovering either a low rank matrix or a
sparse vector from observations of linear combinations of the vector or matrix
elements. Recent methods replace the non-convex regularization with $\ell_1$ or
nuclear norm relaxations. It is well known that this approach can be guaranteed
to recover a near optimal solutions if a so called restricted isometry property
(RIP) holds. On the other hand it is also known to perform soft thresholding
which results in a shrinking bias which can degrade the solution.
In this paper we study an alternative non-convex regularization term. This
formulation does not penalize elements that are larger than a certain threshold
making it much less prone to small solutions. Our main theoretical results show
that if a RIP holds then the stationary points are often well separated, in the
sense that their differences must be of high cardinality/rank. Thus, with a
suitable initial solution the approach is unlikely to fall into a bad local
minima. Our numerical tests show that the approach is likely to converge to a
better solution than standard $\ell_1$/nuclear-norm relaxation even when
starting from trivial initializations. In many cases our results can also be
used to verify global optimality of our method.