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 

Publisher  ArXiv 
Publication status  Published  31 May 2017 
Keywords
 Computer Science  Information Theory
Fingerprint
Dive into the research topics of 'Inexact Gradient Projection and Fast Data Driven Compressed Sensing'. Together they form a unique fingerprint.Projects
 2 Finished

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

Research output
 1 Article

Inexact Gradient Projection and Fast Data Driven Compressed Sensing
Golbabaee, M. & Davies, M., Oct 2018, In: IEEE Transactions on Information Theory. 64, 10, p. 6707  6721Research output: Contribution to journal › Article › peerreview
Open AccessFile