title: Convergence and Stability of a Class of Iteratively Re-weighted Least Squares Algorithms for Sparse Signal Recovery in the Presence of Noise.
abstract: In this paper, we study the theoretical properties of a class of iteratively re-weighted least squares (IRLS) algorithms for sparse signal recovery in the presence of noise. We demonstrate a one-to-one correspondence between this class of algorithms and a class of Expectation-Maximization (EM) algorithms for constrained maximum likelihood estimation under a Gaussian scale mixture (GSM) distribution. The IRLS algorithms we consider are parametrized by 0 <ν≤ 1 andε> 0. The EM formalism, as well as the connection to GSMs, allow us to establish that the IRLS(ν,ε) algorithms minimizeε-smooth versions of the ℓν'norms'. We leverage EM theory to show that, for each 0 <ν≤ 1, the limit points of the sequence of IRLS(ν,ε) iterates are stationary point of theε-smooth ℓν'norm' minimization problem on the constraint set. Finally, we employ techniques from Compressive sampling (CS) theory to show that the class of IRLS(ν,ε) algorithms is stable for each 0 <ν≤ 1, if the limit point of the iterates coincides the global minimizer. For the caseν= 1, we show that the algorithm converges exponentially fast to a neighborhood of the stationary point, and outline its generalization to super-exponential convergence forν< 1. We demonstrate our claims via simulation experiments. The simplicity of IRLS, along with the theoretical guarantees provided in this contribution, make a compelling case for its adoption as a standard tool for sparse signal recovery.
authors.affiliation: Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, Cambridge, MA 02139 ; Department of Anesthesia, Critical Care, and Pain Medicine, Massachusetts General Hospital, Boston, MA 02114.
authors.forename: Behtash
authors.initials: B
authors.lastname: Babadi
authors.affiliation: Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, Cambridge, MA 02139 ; Department of Anesthesia, Critical Care, and Pain Medicine, Massachusetts General Hospital, Boston, MA 02114.
authors.forename: Demba
authors.initials: D
authors.lastname: Ba
authors.affiliation: Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, Cambridge, MA 02139 ; Department of Anesthesia, Critical Care, and Pain Medicine, Massachusetts General Hospital, Boston, MA 02114.
authors.forename: Patrick L
authors.initials: PL
authors.lastname: Purdon
authors.affiliation: Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, Cambridge, MA 02139 ; Department of Anesthesia, Critical Care, and Pain Medicine, Massachusetts General Hospital, Boston, MA 02114 ; Harvard-MIT Division of Health, Sciences and Technology.
authors.forename: Emery N
authors.initials: EN
authors.lastname: Brown