Inexact Gradient Projection and Fast Data Driven Compressed Sensing
- 28 May 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (10) , 6707-6721
Abstract
We study convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets and when both the gradient and projection oracles are computed approximately. We consider different notions of approximation of which we show that the Progressive Fixed Precision (PFP) and the (1+ε)-optimal oracles can achieve the same accuracy as for the exact IPG algorithm. We show that the former scheme is also able to maintain the (linear) rate of convergence of the exact algorithm, under the same embedding assumption. In contrast, the (1+ε)-approximate oracle requires a stronger embedding condition, moderate compression ratios and it typically slows down the convergence. We apply our results to accelerate solving a class of data driven compressed sensing problems, where we replace iterative exhaustive searches over large datasets by fast approximate nearest neighbour search strategies based on the cover tree data structure. For datasets with low intrinsic dimensions our proposed algorithm achieves a complexity logarithmic in terms of the dataset population as opposed to the linear complexity of a brute force search. By running several numerical experiments we conclude similar observations as predicted by our theoretical analysis.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/M019802/1)
- ERC C-SENSE (ERC-ADG-2015-694888)
- Royal Society
This publication has 60 references indexed in Scilit:
- Computational and statistical tradeoffs via convex relaxationProceedings of the National Academy of Sciences, 2013
- Multi-scale geometric methods for data sets II: Geometric Multi-Resolution AnalysisApplied and Computational Harmonic Analysis, 2012
- Accelerated iterative hard thresholdingSignal Processing, 2012
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Multivariate Hyperspectral Raman Imaging Using Compressive DetectionAnalytical Chemistry, 2011
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- Random Projections of Smooth ManifoldsFoundations of Computational Mathematics, 2007
- Nearest-neighbor-preserving embeddingsACM Transactions on Algorithms, 2007
- Tensor rank is NP-completeJournal of Algorithms, 1990
- An Algorithm for Restricted Least Squares RegressionJournal of the American Statistical Association, 1983