Research Repository

Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit

Wen, Jinming and Zhou, Zhengchun and Liu, Zilong and Lai, Ming-Jun and Tang, Xiaohu (2019) 'Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit.' Applied and Computational Harmonic Analysis, 47 (3). 948 - 974. ISSN 1063-5203

[img]
Preview
Text
Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (233kB) | Preview

Abstract

In this paper, we use the block orthogonal matching pursuit (BOMP) algorithm to recover block sparse signals x from measurements y = Ax + v, where v is an ℓ2-bounded noise vector (i.e., kvk2 ≤ ǫ 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+1 < √2/2, then every α-strongly-decaying block K-sparse signal can be exactly or stably recovered by BOMP in K iterations under some conditions on α. Our newly found sufficient condition on the block-RIP of A is less restrictive than that for ℓ1 minimization for this special class of sparse signals. Furthermore, for any K ≥ 1, α > 1 and √2/2 ≤ δ < 1, the recovery of x may fail in K iterations for a sensingmatrix 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 < √2/2, then BOMP is guaranteed to recover some blocks of x if these blocks satisfy a sufficient condition. We further show that this condition is also sharp.

Item Type: Article
Uncontrolled Keywords: Compressed sensing; Block restricted isometry property; Block orthogonal matching pursuit; Block sparse signals; α-strongly-decaying
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 05 Oct 2020 16:19
Last Modified: 05 Oct 2020 17:15
URI: http://repository.essex.ac.uk/id/eprint/26511

Actions (login required)

View Item View Item