  


Quantitative recovery conditions for treebased compressed sensing
Coralia Cartis(cartismaths.ox.ac.uk) Abstract: As shown in [9, 1], signals whose wavelet coefficients exhibit a rooted tree structure can be recovered  using speciallyadapted 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 proportionaldimensional asymptotic framework which enables the quantitative evaluation of recovery guarantees for treebased compressed sensing algorithms. We consider the Iterative Tree Projection (ITP) algorithm [9, 1] with a constant and a variable/practicallyefficient stepsize scheme, respectively. In the context of Gaussian matrices, we apply our simplified asymptotic framework to existing worstcase analysis of ITP, which makes use of the treebased 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 treebased 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 averagecase assumption that the measurements are statistically independent of the signal, we obtain significant quantitative improvements when compared to the treebased RIP analysis; in this case, exact recovery of binary treebased 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: l0minimization, 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/2015 Modify/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  