Convergence of the Generalized Alternating Projection Algorithm for Compressive Sensing

2015/09/04 by Xin Yuan, Hong Jiang, Yuan, Xin +3
Engineering · #Sparse and Compressive Sensing Techniques #Microwave Imaging and Scattering Analysis #Electrical and Bioimpedance Tomography

paper · pdf · doi:10.48550/arxiv.1509.06253

Abstract

The convergence of the generalized alternating projection (GAP) algorithm is studied in this paper to solve the compressive sensing problem \yv = \Amat \xv + \epsilonv. By assuming that \Amat\Amat\ts is invertible, we prove that GAP converges linearly within a certain range of step-size when the sensing matrix \Amat satisfies restricted isometry property (RIP) condition of δ_2K, where K is the sparsity of \xv. The theoretical analysis is extended to the adaptively iterative thresholding (AIT) algorithms, for which the convergence rate is also derived based on δ_2K of the sensing matrix. We further prove that, under the same conditions, the convergence rate of GAP is faster than that of AIT. Extensive simulation results confirm the theoretical assertions.

Citations

• Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

Related

• Generalized Alternating Projection Based Total Variation Minimization for Compressive Sensing
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Alternating direction algorithms for ℓ₀ regularization in compressed sensing
• Alternating Direction Algorithms for ℓ₁-Problems in Compressive Sensing
• Compressive Sensing Using the Entropy Functional