Exact reconstruction analysis of log-sum minimization for compressed sensing

The fact that fewer measurements are needed by log-sum minimization for sparse signal recovery than the L₁-minimization has been observed by extensive experiments. Nevertheless, such a benefit brought by the use of the log-sum penalty function has not been rigorously proved. This paper provides a theoretical justification for adopting the log-sum as an alternative sparsity-encouraging function. We prove that minimizing the log-sum penalty function subject to Az = y is able to yield the exact solution, provided that a certain condition is satisfied. Specifically, our analysis suggests that, for a properly chosen regularization parameter, exact reconstruction can be attained when the restricted isometry constant δ_3k is smaller than one, which presents a less restrictive isometry condition than that required by the conventional L₁-type methods.