Projects per year
Abstract
We study convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly nonconvex) 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+\epsilon)$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+\epsilon)$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.
Original language  English 

Pages (fromto)  6707  6721 
Journal  IEEE Transactions on Information Theory 
Volume  64 
Issue number  10 
Early online date  28 May 2018 
DOIs  
Publication status  Published  Oct 2018 
Keywords
 Convergence
 iterative projected gradient
 approximate updates
 Linear convergence
 compressed sensing
 constrained least squares
 data driven models
 cover trees
 approximate nearest neighbour search
Fingerprint
Dive into the research topics of 'Inexact Gradient Projection and Fast Data Driven Compressed Sensing'. Together they form a unique fingerprint.Projects
 3 Finished

Next Generation Compressive and Computational Sensing and Signal Processing
1/10/16 → 30/09/21
Project: Research

Exploiting low dimensional models in sensing, computation and signal processing
1/09/16 → 31/08/22
Project: Research


Multishot Echo Planar Imaging for accelerated Cartesian MR Fingerprinting: an alternative to conventional spiral MR Fingerprinting
Benjamin, A. J. V., Gómez, P. A., Golbabaee, M., Mahbub, Z., Sprenger, T., Menzel, M. I., Davies, M. & Marshall, I., 10 May 2019, (Epub ahead of print) In: Magnetic Resonance Imaging. 21 p.Research output: Contribution to journal › Article › peerreview
Open AccessFile 
Inexact Gradient Projection and Fast Data Driven Compressed Sensing
Golbabaee, M. & Davies, M. E., 31 May 2017, ArXiv.Research output: Working paper
File
Profiles

Michael Davies
 School of Engineering  Jeffrey Collins Chair of Signal Processing
Person: Academic: Research Active