Non-convex iterative L1 methods for sparse/low-rank reconstruction problems

Event information
Start:
End:
Venue:DM 110

Speaker: Dr. Penghang Yin [UCLA]

Title: Non-convex iterative L1 methods for sparse/low-rank reconstruction problems

Abstract: A compressed sensing (CS) problem can be typically formulated as the minimization of some sparsity-inducing metric subject to linear constraints. In general, non-convex sparse metrics such as Lp (0<p<1) quasi-norm give better model performance than the convex L1 norm. Many existing non-convex CS algorithms, however, suffer from spurious stationary points and perform worse than L1 minimization algorithms empirically, when the sensing matrix possesses highly correlated columns. In this talk, we introduce a general algorithmic framework, based on the difference of convex functions algorithm, for minimizing a class of non-convex sparse metrics. The resulting algorithm calls for solving a sequence of L1-type minimization problems. An exact recovery theory is established to guarantee that the proposed algorithm improves upon L1, irrespective of the conditioning of sensing matrix. As an extension, we further discuss the difference of trace and Frobenius matrix norms and its application to phase retrieval problem.