Near optimal bound of orthogonal matching pursuit using restricted isometric constant

Wang Jian, Kwon Seokbeop, Shim, Shim Byonghyo

Description

As a paradigm for reconstructing sparse signals using a set of under sampled measurements, compressed sensing has received much attention in recent years. In identifying the sufficient condition under which the perfect recovery of sparse signals is ensured, a property of the sensing matrix referred to as the restricted isometry property (RIP) is popularly employed. In this article, we propose the RIP based bound of the orthogonal matching pursuit (OMP) algorithm guaranteeing the exact reconstruction of sparse signals. Our proof is built on an observation that the general step of the OMP process is in essence the same as the initial step in the sense that the residual is considered as a new measurement preserving the sparsity level of an input vector. Our main conclusion is that if the restricted isometry constant δ K of the sensing matrix satisfies δ K < K - 1 K - 1 + K then the OMP algorithm can perfectly recover K (> 1)-sparse signals from measurements. We show that our bound is sharp and indeed close to the limit conjectured by Dai and Milenkovic.

Sujets

• Compressed sensing
• Support

Informations

• Publié par: biomed
• Publié le: 01 janvier 2012
• Nombre de lectures: 2
• Langue: English

Extrait

Wanget al.EURASIP Journal on Advances in Signal Processing2012,2012:8 http://asp.eurasipjournals.com/content/2012/1/8

R E S E A R C H

Near optimal bound of pursuit using restricted * Jian Wang, Seokbeop Kwon and Byonghyo Shim

Open Access

orthogonal matching isometric constant

Abstract As a paradigm for reconstructing sparse signals using a set of under sampled measurements, compressed sensing has received much attention in recent years. In identifying the sufficient condition under which the perfect recovery of sparse signals is ensured, a property of the sensing matrix referred to as the restricted isometry property (RIP) is popularly employed. In this article, we propose the RIP based bound of the orthogonal matching pursuit (OMP) algorithm guaranteeing the exact reconstruction of sparse signals. Our proof is built on an observation that the general step of the OMP process is in essence the same as the initial step in the sense that the residual is considered as a new measurement preserving the sparsity level of an input vector. Our main conclusion is that if the restricted isometry constantδ K of the sensing matrix satisfies K−1 δ K < K−1 +K

then the OMP algorithm can perfectly recoverK(> 1)sparse signals from measurements. We show that our bound is sharp and indeed close to the limit conjectured by Dai and Milenkovic. Keywords:compressed sensing, sparse signal, support, orthogonal matching pursuit, restricted isometric property

1 Introduction As a paradigm to acquire sparse signals at a rate signifi cantly below Nyquist rate, compressive sensing has received much attention in recent years [117]. The goal of compressive sensing is to recover the sparse vector using small number of linearly transformed measure ments. The process of acquiring compressed measure ments is referred to assensingwhile that of recovering the original sparse signals from compressed measure ments is calledreconstruction. In the sensing operation,Ksparse signal vectorx, i.e., ndimensional vector having at mostKnonzero ele ments, is transformed intomdimensional signal (mea surements)yvia a matrix multiplication withF. This process is expressed as

y=x.

(1)

* Correspondence: [e-mail] School of Information and Communication, Korea University, Seoul 136713, Korea

Sincen > mfor most of the compressive sensing scenarios, the system in (1) can be classified as an underdetermined system having more unknowns than observations, and hence, one cannot accurately solve this inverse problem in general. However, due to the prior knowledge of sparsity information, one can recon structxperfectly via properly designed reconstruction algorithms. Overall, commonly used reconstruction stra tegies in the literature can be classified into two cate gories. The first class is linear programming (LP) techniques includingℓ 1 minimization and its variants. Donoho [10] and Candes [13] showed that accurate recovery of the sparse vectorxfrom measurementsyis possible usingℓ 1 minimization technique if the sensing matrixFsatisfiesrestricted isometry property(RIP) with a constant parameter calledrestricted isometry constant. For each positive integerK, the restricted isometric con stantδ K of a matrixFis defined as the smallest number satisfying

2 2 2  x  ≤ (1−δ K ) 2  x  ≤ (1 +δ K )  x  2 2

(2)

© 2012 Wang et al; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.