UC Irvine

An algorithmic framework, based on the difference of convex functions algorithm, is proposed

for minimizing difference of $\ell_1$ and $\ell_2$ norms ($\ell_{1-2}$ minimization) as well as a wide class of concave sparse metrics for compressed sensing problems. The resulting

algorithm iterates a sequence of $\ell_1$ minimization problems.

An exact sparse recovery theory is established to show that the proposed framework always

improves on the basis pursuit ($\ell_1$ minimization) and inherits robustness from it.

Numerical examples on success rates of sparse solution recovery illustrate further that,

unlike most existing non-convex compressed sensing solvers

in the literature, our method always out-performs basis pursuit, no matter how ill-conditioned the measurement matrix is.

As the counterpart of $\ell_{1-2}$ minimization for low-rank matrix recovery, we present a phase retrieval method via minimization of the difference of trace and Frobenius norms which we call

PhaseLiftOff. The associated least squares minimization with this penalty as regularization

is equivalent to the original rank-one least squares

problem under a mild condition on the measurement noise.

Numerical results show that PhaseLiftOff outperforms the convex PhaseLift and its non-convex variant (log-determinant regularization), and

successfully recovers signals near the theoretical lower limit on the number of measurements without the noise.