Download or read book Non-convex Optimization Methods for Sparse and Low-rank Reconstruction written by Penghang Yin and published by . This book was released on 2016 with total page 93 pages. Available in PDF, EPUB and Kindle. Book excerpt: An algorithmic framework, based on the difference of convex functions algorithm, is proposed for minimizing difference of ℓ1 and ℓ 2 norms (ℓ1-2 minimization) as well as a wide class of concave sparse metrics for compressed sensing problems. The resulting algorithm iterates a sequence of ℓ1 minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit (ℓ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 ℓ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.