Inexact Gradient Projection and Fast Data Driven Compressed Sensing

Mohammad Golbabaee, Mike E. Davies

Abstract

The Iterative Projected Gradient (IPG) algorithm is a foundational tool for compressed sensing (CS), yet its projection step often becomes a computational bottleneck when applied to complex, data-driven signal models. This paper investigates the use of inexact (approximate) projections—specifically through fixed precision, progressively tightening precision, or relative error bounds. We demonstrate that these approximations can accelerate the algorithm by up to 100x without compromising reconstruction accuracy or convergence rates, provided certain embedding conditions are met.

Introduction

Compressed Sensing (CS) enables the reconstruction of high-dimensional signals from a minimal number of measurements by leveraging underlying low-dimensional structures, such as sparsity or manifold constraints. The standard approach for reconstruction is the Iterative Projected Gradient (IPG) algorithm, which alternates between a gradient descent step to minimize measurement error and a projection step to enforce the signal model.

In modern "data-driven" CS, the signal model is often defined by a massive dictionary of signal patches (e.g., in Magnetic Resonance Fingerprinting). In these cases, the projection step requires finding the nearest neighbor in a dictionary containing hundreds of thousands of points. Performing an exhaustive search at every iteration is computationally prohibitive. This research explores whether "cheating" via approximate searches can maintain the stability and convergence of the IPG framework.

Methodology: Inexact Oracles

The authors provide a rigorous theoretical analysis of IPG using three distinct types of "inexact oracles" for the projection and gradient steps:

  1. Fixed Precision (FP): The approximation maintains a constant, bounded additive error. While computationally simple, this approach introduces a floor on reconstruction accuracy.
  2. Progressive Fixed Precision (PFP): The algorithm begins with coarse, fast approximations and gradually increases precision as iterations progress. This allows for rapid initial convergence followed by high-fidelity refinement.
  3. $(1+\epsilon)$-approximate: This oracle identifies a solution within a relative multiplicative factor $(1+\epsilon)$ of the optimal projection. This is highly compatible with modern Approximate Nearest Neighbor (ANN) data structures.

To ensure convergence, the authors introduce a "hybrid local-uniform linear embedding" assumption. This is a relaxed version of the standard Restricted Isometry Property (RIP), tailored for localized manifold structures rather than global sparsity.

Data-Driven Implementation via Cover Trees

To translate theory into practice, the authors utilize cover trees to organize signal dictionaries. This data structure facilitates efficient ANN searches, reducing the complexity of the projection step from $O(d)$ (linear with dictionary size) to $O(\log d)$ (logarithmic). This transition is critical for making data-driven CS viable for real-time or large-scale applications.

Experimental Setup and Datasets

The algorithms were evaluated across several low-dimensional manifold datasets:

  • Synthetic Manifolds: S-Manifold, Swiss roll, and Oscillating wave datasets (5,000 points each).
  • Physics-driven Data: A Magnetic Resonance Fingerprinting (MRF) dictionary (29,760 points) generated via Bloch dynamic equations for MRI tissue relaxation times.

Key Insights and Results

The "Free Lunch" of Progressive Precision

The PFP approach emerged as a highly efficient strategy. By starting with low-precision projections and tightening the bounds over time, the algorithm achieves the same final accuracy and linear convergence rate as an exact IPG algorithm but at a fraction of the computational cost.

Speed and Scalability

The $(1+\epsilon)$-ANN IPG algorithm demonstrated a 4x to 10x acceleration over exact cover tree searches. When compared to traditional brute-force dictionary searches, the approximate methods yielded a 100x speedup. This performance gap is expected to widen as dictionary sizes increase.

Phase Transitions and Sensitivity

While the $(1+\epsilon)$ oracle is the fastest, it comes with a trade-off. Empirical results confirmed that relative error approximations require a higher sampling ratio (more measurements) to remain stable. In extreme undersampling regimes, the $(1+\epsilon)$ method is prone to "noise folding," whereas the PFP-ANN method remains robust.

Conclusion and Future Work

This work demonstrates that exactness in the projection step is not a prerequisite for successful signal reconstruction in compressed sensing. By employing inexact oracles and efficient data structures like cover trees, data-driven CS can be scaled to handle massive, high-dimensional dictionaries.

Future research will focus on extending these robustness proofs to convex CS settings and exploring "Head approximation" techniques to remove the $\epsilon$ dependency in gradient estimation. Additionally, the authors aim to integrate these findings with "sketching" techniques for even larger-scale inverse problems.

Summary updated

BibTeX
@article{golbabaee2018inexact,
  author = {Mohammad Golbabaee and Mike E. Davies},
  title = {{Inexact Gradient Projection and Fast Data Driven Compressed Sensing}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  doi = {10.1109/tit.2018.2841379},
}
Figure