Shifting Inequality and Recovery of Sparse Signals

In this paper, we present a concise and coherent analysis of the constrained ¿ 1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, i...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2010-03, Vol.58 (3), p.1300-1308
Main Authors: Cai, T.T., Lie Wang, Guangwu Xu
Format: Article
Language:English
Subjects:
Applied sciences
Coherence
Compressed sensing
Electrical engineering
ell_{1} minimization
Exact sciences and technology
Inequalities
Information, signal and communications theory
Magnetic field measurement
Mathematics
Minimization
Minimization methods
Miscellaneous
Noise measurement
Norms
Optimization
Recovering
Recovery
restricted isometry property
shifting inequality
Signal analysis
Signal processing
Sparse matrices
sparse recovery
Statistics
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a concise and coherent analysis of the constrained ¿ 1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via ¿ 1 minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the ¿ 2 norm of a subsequence in terms of the ¿ 1 norm of another subsequence by shifting the elements to the upper end.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2009.2034936