Optimization Online


Quantitative recovery conditions for tree-based compressed sensing

Coralia Cartis(cartis***at***maths.ox.ac.uk)
Andrew Thompson(thompson***at***maths.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/2015
Entry Accepted: 09/20/2015
Entry Last Modified: 09/20/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society