Inexact Gradient Projection and Fast Data Driven Compressed Sensing

Mohammad Golbabaee, Mike E. Davies

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets 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 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 data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set 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 languageEnglish
Article number18079646
Pages (from-to)6707-6721
Number of pages15
JournalIEEE Transactions on Information Theory
Volume64
Issue number10
Early online date28 May 2018
DOIs
Publication statusPublished - 31 Oct 2018

Cite this

Inexact Gradient Projection and Fast Data Driven Compressed Sensing. / Golbabaee, Mohammad; Davies, Mike E.

In: IEEE Transactions on Information Theory, Vol. 64, No. 10, 18079646, 31.10.2018, p. 6707-6721.

Research output: Contribution to journalArticle

@article{65c09316e1944ef9853536218c1bced2,
title = "Inexact Gradient Projection and Fast Data Driven Compressed Sensing",
abstract = "We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets 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 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 data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set 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.",
author = "Mohammad Golbabaee and Davies, {Mike E.}",
year = "2018",
month = "10",
day = "31",
doi = "10.1109/TIT.2018.2841379",
language = "English",
volume = "64",
pages = "6707--6721",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "10",

}

TY - JOUR

T1 - Inexact Gradient Projection and Fast Data Driven Compressed Sensing

AU - Golbabaee, Mohammad

AU - Davies, Mike E.

PY - 2018/10/31

Y1 - 2018/10/31

N2 - We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets 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 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 data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set 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.

AB - We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets 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 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 data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set 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.

U2 - 10.1109/TIT.2018.2841379

DO - 10.1109/TIT.2018.2841379

M3 - Article

VL - 64

SP - 6707

EP - 6721

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 10

M1 - 18079646

ER -