Convergence and stability analysis of iteratively reweighted least squares for noisy block sparse recovery

This paper considers the theoretical properties of iteratively reweighted least squares algorithm for noisy block sparse recovery problem (BIRLS for short). Li et al. used numerical experiments to show the remarkable performance of BIRLS algorithm for recovering a block sparse signal in noiseless measurement case, but no convergence analysis was given. In this paper, we focus on providing convergence, convergence rate and stability analysis of BIRLS algorithm for block sparse recovery in the presence of noise. The convergence of BIRLS is proved strictly. Furthermore, when the linear measurement matrix Asatisfies the block restricted isometry property (abbreviated as block RIP), we show that BIRLS algorithm is stable and give the error analysis of BIRLS algorithm. We also characterize the convergence rate of the BIRLS algorithm, which implies global linear convergence for p = 1and local super-linear convergence for 0 < p < 1. The simplicity of BIRLS algorithm, along with the theoretical provided in this paper, make a compelling case for its adoption as a standard tool for block sparse recovery. (c) 2021 Published by Elsevier Inc.

Automated summary

This paper provides convergence, convergence rate, and stability analysis of the BIRLS algorithm for block sparse recovery in the presence of noise. The convergence and stability of BIRLS are proved, and the convergence rate is characterized.