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.
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