Exact Reconstruction Analysis of Log-Sum Minimization for Compressed Sensing

Abstract

The fact that fewer measurements are needed by log-sum minimization for sparse signal recovery than the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -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 δ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3K</sub> is smaller than one, which presents a less restrictive isometry condition than that required by the conventional ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -type methods.