University of Surrey

Test tubes in the lab Research in the ATI Dance Research

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

Wen, Jinming, Zhou, Zhengchun, Liu, Zilong, Lai, Ming-Jun and Tang, Xiaohu (2018) Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit Applied and Computational Harmonic Analysis.

[img]
Preview
Text
Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit.pdf - Accepted version Manuscript

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
Divisions : Faculty of Engineering and Physical Sciences > Electronic Engineering
Authors :
NameEmailORCID
Wen, Jinming
Zhou, Zhengchun
Liu, Zilongzilong.liu@surrey.ac.uk
Lai, Ming-Jun
Tang, Xiaohu
Date : 7 February 2018
DOI : 10.1016/j.acha.2018.02.002
Copyright Disclaimer : © 2018 Elsevier Inc. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Uncontrolled Keywords : Compressed sensing; Block restricted isometry property; Block orthogonal matching pursuit; Block sparse signals; α-strongly-decaying
Depositing User : Clive Harris
Date Deposited : 12 Sep 2018 15:04
Last Modified : 08 Feb 2019 02:08
URI: http://epubs.surrey.ac.uk/id/eprint/849269

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800