On Landscape of Nonconvex Regularized Least Squares for Sparse Support Recovery

Exact sparse support recovery from noisy deterministic Fourier measurements is studied in this letter. The ideal ℓ0 -regularized least squares (LS) program is known to have strict local minimizers for multiple sparse supports. By applying a specific non-convex surrogate of the ℓ0 -regularizer, we show that, under certain conditions, the set of local minimizers with particularly separated supports is a singleton. Thus, any converging algorithms that can enforce the corresponding separation constraint will lead to the true support as the unique solution. In this regard, we construct a novel optimal mapping operator that can fulfill the separation condition, and several empirically effective algorithms are developed. The simulation results demonstrate the theoretical claims made in this letter.