Inexact Gradient Projection and Fast Data Driven Compressed Sensing

DOI10.1109/TIT.2018.2841379MaRDI QIDQ4682945zbMATH OpenFDO

Authors Mohammad Golbabaee, M. E. Davies

Publication date 19 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.00092

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

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.

Cited in

(11)

• On the inexact scaled gradient projection method
• Inexact gradient projection method with relative error tolerance
• scientific article; zbMATH DE number 6907423 (Why is no real title available?)
• Spectral Compressed Sensing via Projected Gradient Descent
• The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem
• CoverBLIP: accelerated and scalable iterative matched-filtering for magnetic resonance fingerprint reconstruction
• Jointly low-rank and bisparse recovery: questions and partial answers
• A box constrained gradient projection algorithm for compressed sensing
• Incorporating multiple a priori information for inverse problem by inexact scaled gradient projection
• Extragradient method with feasible inexact projection to variational inequality problem
• An improved HZ CG method with inexact projections for solving convex-constrained nonlinear equations and its applications

This page was built for publication: Inexact Gradient Projection and Fast Data Driven Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682945)