Compressed sensing recovery via nonconvex shrinkage penalties. (18th May 2016)

• Record Type: Journal Article
• Authors: Woodworth, Joseph; Chartrand, Rick
• Is Part Of: Inverse problems. Volume 32:Number 7(2016:Jul.)
• Publication Date: 2016-05-18
• Subjects: compressed sensing -- nonconvexity -- relaxation -- exact recovery -- stability -- convergence; 46N10 -- 94A12 -- 65K05 -- 90C26; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/0266-5611/32/7/075004
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: The ℓ 0 minimization of compressed sensing is often relaxed to ℓ 1, which yields easy computation using the shrinkage mapping known as soft thresholding, and can be shown to recover the original solution under certain hypotheses. Recent work has derived a general class of shrinkages and associated nonconvex penalties that better approximate the original ℓ 0 penalty and empirically can recover the original solution from fewer measurements. We specifically examine p-shrinkage and firm thresholding . In this work, we prove that given data and a measurement matrix from a broad class of matrices, one can choose parameters for these classes of shrinkages to guarantee exact recovery of the sparsest solution. We further prove convergence of the algorithm iterative p-shrinkage (IPS) for solving one such relaxed problem.