As shown in [9, 1], 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 algorithms. We consider the Iterative Tree Projection (ITP) algorithm [9, 1] with a constant and a variable/practically-efficient stepsize scheme, respectively. In the context of Gaussian matrices, we apply our simplified asymptotic framework to existing worst-case analysis of ITP, which makes use of the tree-based Restricted Isometry Property (RIP). 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. In particular, we prove that exact recovery of binary tree-based signals from noiseless Gaussian measurements is asymptotically guaranteed for ITP provided $n\geq 115k$ (constant stepsize) and $n\geq 683k$ (variable stepsize). Within the same framework, we then obtain quantitative results based on a new method of analysis, recently introduced in [14], which considers the fixed points of the same ITP algorithmic variants. By exploiting the realistic average-case assumption that the measurements are statistically independent of the signal, we obtain significant quantitative improvements when compared to the tree-based RIP analysis; in this case, exact recovery of binary tree-based signals from noiseless Gaussian measurements is asymptotically guaranteed for ITP provided $n\geq 50k$ (constant stepsize) and $n\geq 55k$ (variable stepsize). All our results are also extended to the more realistic case in which measurements are corrupted by noise.
Citation
NA Technical Report, Mathematical Institute, Oxford University, 2015.
Article
View Quantitative recovery conditions for tree-based compressed sensing