2016/05/10 by Wen, Jinming, Zhou, Zhengchun, Liu, Zilong +2
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1605.02894
In this paper, we use the block orthogonal matching pursuit (BOMP) algorithm to recover block sparse signals \x from measurements \y=\A\x+\v, where \v is an ℓ2-bounded noise vector (i.e., ‖\v‖2≤ ε for some constant ε). We investigate some sufficient conditions based on the block restricted isometry property (block-RIP) for exact (when \v=\0) and stable (when \v≠\0) recovery of block sparse signals \x. First, on the one hand, we show that if \A satisfies the block-RIP with δK+1<1/√(K+1), then every block K-sparse signal \x can be exactly or stably recovered by BOMP in K iterations. On the other hand, we show that, for any K≥ 1 and 1/√(K+1)≤ δ<1, there exists a matrix \A satisfying the block-RIP with δK+1=δ and a block K-sparse signal \x such that BOMP may fail to recover \x in K iterations. Then, we study some sufficient conditions for recovering block α-strongly-decaying K-sparse signals. We show that if \A satisfies the block-RIP with δK+11 and √(2)/2≤ δ<1, the recovery of \x may fail in K iterations for a sensing matrix \A which satisfies the block-RIP with δK+1=δ. Finally, we study some sufficient conditions for partial recovery of block sparse signals. Specifically, if \A satisfies the block-RIP with δK+1