Shifting Inequality and Recovery of Sparse Signals
Tony Cai, Lie Wang and Guangwu Xu
-
Abstract:
In this paper we present a concise and coherent analysis of the constrained l1 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 l1 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 l2 norm of a subsequence in terms of the l1 norm of another subsequence by shifting the elements to the upper end.
- Paper:
pdf file.
- Other related papers:
Cai, T., Xu, G. & Zhang, J. (2009).
On recovery of sparse signals via l1 minimization.
IEEE Transactions on Information Theory 55 , 3388-3397.Cai, T., Wang, L. & Xu, G. (2010).
Stable recovery of sparse signals and an oracle inequality.
IEEE Transactions on Information Theory 56 , 3516-3522.