Generalized alternating projection for weighted-l2,1 minimization with applications to model-based compressive sensing

Xuejun Liao, Hui Li, Lawrence Carin

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

Abstract

We consider the group basis pursuit problem, which extends basis pursuit by replacing the l1 norm with a weighted-L2,1 norm. We provide an anytime algorithm, called generalized alternating projection (GAP), to solve this problem. The GAP algorithm extends classical alternating projection to the case in which projections are performed between convex sets that undergo a systematic sequence of changes. We prove that, under a set of group-restricted isometry property (group-RIP) conditions, the reconstruction error of GAP monotonically converges to zero. Thus the algorithm can be interrupted at any time to return a valid solution and can be resumed subsequently to improve the solution. This anytime convergence property saves iterations on retracting and correcting mistakes, which, along with an effective acceleration scheme, makes GAP converge fast. Moreover, the periteration computation is inexpensive, consisting of sorting of a linear array followed by groupwise thresholding and linear transform of vectors for which fast algorithms often exist. We evaluate the algorithmic performance through extensive experiments in which GAP is compared to other state-of-the-art algorithms and applied to compressive sensing of natural images and video. © 2014 Society for Industrial and Applied Mathematics.
Original languageEnglish (US)
Pages (from-to)797-823
Number of pages27
JournalSIAM Journal on Imaging Sciences
Volume7
Issue number2
DOIs
StatePublished - Jun 26 2014
Externally publishedYes

Fingerprint Dive into the research topics of 'Generalized alternating projection for weighted-l2,1 minimization with applications to model-based compressive sensing'. Together they form a unique fingerprint.

Cite this