TY - JOUR

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

AU - Liao, Xuejun

AU - Li, Hui

AU - Carin, Lawrence

N1 - Generated from Scopus record by KAUST IRTS on 2021-02-09

PY - 2014/6/26

Y1 - 2014/6/26

N2 - 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.

AB - 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.

UR - http://epubs.siam.org/doi/10.1137/130936658

UR - http://www.scopus.com/inward/record.url?scp=84903377281&partnerID=8YFLogxK

U2 - 10.1137/130936658

DO - 10.1137/130936658

M3 - Article

SN - 1936-4954

VL - 7

SP - 797

EP - 823

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

IS - 2

ER -