An Optimal Condition for the Block Orthogonal Matching Pursuit Algorithm

作者：Wen, Jinming; Chen, Huangke; Zhou, Zhengchun^*

来源：IEEE Access, 2018, 6: 38179-38185.

DOI：10.1109/ACCESS.2018.2853158

• Compressed sensing
• block orthogonal matching pursuit
• block mutual coherence
• sub-coherence
• support recovery

Recovery of the support of a block K-sparse signal x from a linear model y = Ax + v, where A is a sensing matrix and v is a noise vector, arises from many applications. The block orthogonal matching pursuit (BOMP) algorithm is a popular block sparse recovery algorithm and has received much attention in the recent decade. It was proved by Eldar et al. that the BOMP can recover the positions Omega of the nonzero blocks of any block K-sparse vector x with a block length d in the noisy case (under certain condition on x and v) and can exactly recover x in the noiseless case in K iterations if the block mutual coherence mu(A) and sub-coherence nu(A) of A satisfy (2K - 1)d mu(A) + (d - 1)nu(A) < 1. In this paper, we first improve and develop sufficient conditions of recovering Omega with the BOMP algorithm under the l(2)-bounded and l(infinity)-bounded noises, respectively. Then, we show that for any given positive integers K and d, there always exist a block K-sparse vector x with the block length d, and a sensing matrix A with (2K - 1)d mu(A) + (d - 1)nu(A) = 1 such that the BOMP is not able to recover x from y = Ax in K iterations. This indicates that the condition proposed by Eldar et al. is sharp in terms of the condition on A.

• 出版日期2018
• 单位西南交通大学; 中国人民解放军国防科学技术大学; 暨南大学