Progressive Stochastic Greedy Sparse Reconstruction and Support Selection

Abolfazl Hashemi, Haris Vikalo, Gustavo de VecianaarXiv 2019 · arXiv

Abstract

Sparse reconstruction and sparse support selection—the tasks of inferring an $m$-dimensional sparse vector $\mathbf{x}$ with $k$ nonzero entries from $n$ linear measurements—are fundamental to machine learning and signal processing. While standard greedy algorithms achieve optimal sampling complexity $n = \mathcal{O}(k\log\frac{m}{k})$, their $\mathcal{O}(mk)$ computational complexity is often prohibitive for large-scale datasets. This paper introduces Progressive Stochastic Greedy (PSG), the first sparse support selection algorithm for arbitrary sparse vectors that achieves exact identification with $\tilde{\mathcal{O}}(m)$ computational complexity. By progressively expanding the search space, PSG maintains the sampling efficiency of greedy methods while significantly reducing the computational burden.

The Performance-Complexity Wall

Many critical tasks, such as feature selection and sensor placement, involve maximizing a "weakly submodular" function. The standard Greedy algorithm is the benchmark for accuracy, iteratively selecting the element with the highest marginal gain. However, its cost—$O(mk)$ function evaluations—scales poorly.

To address this, researchers previously proposed "Stochastic Greedy" methods that search a fixed-size random subset at each step. While faster, this paper proves a critical limitation: as problem size grows, fixed-sampling methods fail to find the exact optimal subset with overwhelming probability. This creates a "performance cliff" where randomized methods become unreliable for truly large-scale systems.

Methodology: Progressive Sampling

The core innovation of Progressive Stochastic Greedy (PSG) is its progressive sampling schedule. Instead of a static search space, PSG starts with a very small random subset and gradually increases the sample size as the algorithm progresses. In the $i$-th iteration, it samples $r_i = \frac{m}{k-i} \log \frac{1}{\epsilon}$ elements.

  • Early Stages: The search space is minimal, allowing for rapid initial progress.
  • Late Stages: As the "easy" elements are selected and the remaining optimal elements become harder to distinguish, the search space expands (potentially to the full ground set).

This "soft transition" ensures that the algorithm maintains the high success probability of the full Greedy algorithm while keeping computational complexity near $\tilde{O}(m)$.

Experimental Results

Sparse Recovery and Support Selection

In Monte Carlo simulations for sparse recovery, the authors compared PSG against fixed-sampling strategies. The results, illustrated in Figure 3, confirm the theoretical predictions. While PSG (panel a) maintains a recovery rate near 1.0 across varying sparsity levels $k$, fixed-sampling methods (panels b and c) see their success rates plummet toward zero as $k$ increases. This demonstrates that an increasing search space is a theoretical necessity for exact identification in large-scale problems.

Comparison of recovery performance: (a) PSG maintains high accuracy across different error tolerances (β), while fixed-sampling strategies (b) and (c) fail as the problem size scales.

Real-World Applications

  • Column Subset Selection (EYaleB): On the EYaleB face dataset, PSG matched the reconstruction error and clustering accuracy of the full Greedy algorithm but reduced the oracle complexity (number of function evaluations) from approximately $10^7$ to $10^5$.
  • Autonomous Driving: In a multi-object tracking scenario with eight sensors, PSG achieved tracking accuracy identical to using the full observation set but with a significantly lower and more stable runtime, even during spikes in sensor data.

Conclusion

PSG bridges the gap between fast-but-unreliable randomized greedy methods and slow-but-accurate standard greedy optimization. It hits a computational "sweet spot," incurring a complexity of $O(m \log(1/\epsilon) \log k)$—only slightly higher than basic Stochastic Greedy but orders of magnitude lower than standard Greedy. Future work includes developing adaptive schedules that adjust search space size dynamically based on observed marginal gains and extending the framework to distributed computing environments.

Summary updated

Abstract

Sparse reconstruction and sparse support selection, i.e., the tasks of inferring an arbitrary $m$-dimensional sparse vector $\mathbf{x}$ having $k$ nonzero entries from $n$ measurements of linear combinations of its components, are often encountered in machine learning, computer vision, and signal processing. Existing greedy-based algorithms achieve optimal $n = \mathcal{O}(k\log\frac{m}{k})$ sampling complexity with computational complexity that is linear in the size of the data $m$ and cardinality constraint $k$. However, the ${\mathcal{O}}(mk)$ computational complexity is still prohibitive for large-scale datasets. In this paper, we present the first sparse support selection algorithm for arbitrary sparse vectors that achieves exact identification of the optimal subset from $n = \mathcal{O}(k\log\frac{m}{k})$ measurements with $\tilde{\mathcal{O}}(m)$ computational complexity. The proposed scheme utilizes the idea of randomly restricting search space of the greedy method in a progressive manner to reduce the computational cost while maintaining the same order of sampling complexity as the existing greedy schemes. Simulation results including an application of the algorithm to the task of column subset selection demonstrate efficacy of the proposed algorithm.
BibTeX
@misc{hashemi2019progressive,
  author = {Abolfazl Hashemi and Haris Vikalo and Gustavo de Veciana},
  title = {{Progressive Stochastic Greedy Sparse Reconstruction and Support Selection}},
  year = {2019},
  eprint = {1907.09064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.09064},
}
Figure