Online performance guarantees for sparse recovery

A K*-sparse vector x* ∈ RN produces measurements via linear dimensionality reduction as u = Φx* +n, where Φ ∈ RM×N (M <; N), and n ∈ RM consists of independent and identically distributed, zero mean Gaussian entries with variance σ2. An algorithm, after its execution, determines a vector x̃ that has K-nonzero entries, and satisfies ||u - Φx̃|| ≤ ϵ. How far can x̃ be from x*? When the measurement matrix Φ provides stable embedding to 2K-sparse signals (the so-called restricted isometry property), they must be very close. This paper therefore establishes worst-case bounds to characterize the distance ||x̃- x*|| based on the online meta information. These bounds improve the pre-run algorithmic recovery guarantees, and are quite useful in exploring various data error and solution sparsity trade-offs. We also evaluate the performance of some sparse recovery algorithms in the context of our bound.

Presented at:
2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, May 22-27, 2011

 Record created 2014-12-05, last modified 2019-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)