- Quantitative recovery conditions for tree-based compressed sensing Coralia Cartis(cartismaths.ox.ac.uk) Andrew Thompson(thompsonmaths.ox.ac.uk) Abstract: 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. Keywords: l0-minimization, wavelets, compressed sensing, sparse optimization Category 1: Applications -- Science and Engineering Category 2: Nonlinear Optimization Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: NA Technical Report, Mathematical Institute, Oxford University, 2015. Download: [PDF]Entry Submitted: 09/20/2015Entry Accepted: 09/20/2015Entry Last Modified: 09/20/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.