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 ℓ₁-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 ℓ₁-type methods.