Back to Search
Start Over
Quantitative Recovery Conditions for Tree-Based Compressed Sensing.
- Source :
-
IEEE Transactions on Information Theory . Mar2017, Vol. 63 Issue 3, p1555-1571. 17p. - Publication Year :
- 2017
-
Abstract
- As shown by Blumensath and Davies (2009) and Baraniuk et al. (2010), signals whose wavelet coefficients exhibit a rooted tree structure can be recovered using specially adapted compressed sensing algorithms from just n=\mathcal O(k) measurements, where $k$ is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework, which enables the quantitative evaluation of recovery guarantees for tree-based compressed sensing. In the context of Gaussian matrices, we apply this framework to existing worst-case analysis of the iterative tree projection (ITP) algorithm, which makes use of the tree-based restricted isometry property (RIP). Within the same framework, we then obtain quantitative results based on a new method of analysis, which considers the fixed points of the algorithm. By exploiting the realistic average-case assumption that the measurements are statistically independent of the signal, we obtain significant quantitative improvements when compared with the tree-based RIP analysis. Our results have a refreshingly simple interpretation, explicitly determining a bound on the number of measurements that are required as a multiple of the sparsity. For example, we prove that exact recovery of binary tree-based signals from noiseless Gaussian measurements is asymptotically guaranteed for ITP with constant stepsize provided $n\geq 50k$ . All our results extend to the more realistic case in which measurements are corrupted by noise. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 121340787
- Full Text :
- https://doi.org/10.1109/TIT.2016.2633415