Abstract
The Alternating Subspace Method (ASM) is a novel algorithm for sparse signal recovery that bridges the gap between fast "greedy" search methods and mathematically rigorous "splitting" optimization frameworks. By confining computationally intensive data-fidelity operations to a dynamically identified "active" subspace, ASM achieves significant acceleration—up to 11x over standard methods—while maintaining global convergence guarantees and high precision.
Introduction: The Sparse Recovery Dilemma
In compressed sensing, the objective is to recover a high-dimensional sparse signal $x$ from a limited set of noisy measurements $y = Ax + w$. This "needle in a haystack" problem is foundational to modern medical imaging, wireless communications, and radar systems.
Existing solutions typically fall into two categories:
- Greedy Methods (e.g., OMP): These are computationally efficient as they iteratively select likely active components. However, they often lack robustness and struggle with complex signal priors.
- Splitting Methods (e.g., ADMM, ISTA): These offer mathematical flexibility and convergence guarantees but are often slow. Their primary bottleneck is the "data fidelity" step, which requires solving large-scale linear systems across the entire signal space.
The Alternating Subspace Method (ASM) addresses this trade-off by integrating subspace-restricted search into the robust Alternating Direction Method of Multipliers (ADMM) framework.
The Alternating Subspace Method
The core innovation of ASM is Subspace Fidelity. Instead of performing Regularized Least Squares (RLS) on the full $N$-dimensional space, ASM identifies a promising "active set" of indices and restricts data matching to this low-dimensional subspace.
As shown in the pseudocode above, the algorithm iterates through three primary stages:
- Denoising: A proximal operator (e.g., soft-thresholding) estimates the signal and identifies the current "active" subspace $E^k$.
- Subspace Fidelity: The data-matching problem is solved strictly within the restricted subspace $E^k$, transforming a massive matrix operation into a significantly smaller, faster computation.
- Averaging: To prevent oscillation and ensure stability, the new estimate is averaged with the previous iteration's result.
Crucially, the authors establish global convergence through "proximal residual control," ensuring that these computational shortcuts do not compromise the final solution's accuracy.
Experimental Validation
ASM was evaluated across several challenging scenarios:
- Synthetic LASSO Problems: Testing against various measurement matrices (Gaussian, Row-Orthogonal, Toeplitz, P-DCT, and Bernoulli).
- Massive MIMO Channel Estimation: Using the WINNER2 model to simulate 5G/6G environments.
- Dynamic Compressed Sensing: Tracking moving terminals in a TDD wireless system under 3GPP CDL-C channel conditions.
Key Results and Insights
The primary advantage of ASM is its ability to "shrink" the null space. In sparse recovery, the error in the null space (components the measurements cannot see) often limits convergence speed. By forcing the solution into a low-dimensional subspace, ASM triggers a rapid local contraction toward the true signal.
As illustrated in the convergence plots:
- Speed: In dynamic channel tracking at 40 dB SNR, ASM achieved an 11.4x speedup over standard ADMM and a 3.89x speedup over the state-of-the-art SSNAL method.
- Precision: ASM exhibits "local geometric convergence." Once the correct support is identified, the algorithm homes in on the exact values with extreme speed.
- Flexibility: Unlike second-order methods like SSNAL, ASM can easily incorporate sophisticated denoisers, such as Hidden Markov Chains (HMC), to handle structured sparsity.
Conclusion and Future Work
ASM represents a significant step forward in efficient sparse signal recovery, offering the speed of greedy algorithms with the reliability of splitting methods. While the current implementation requires some empirical parameter tuning, its performance in massive MIMO and dynamic tracking scenarios is compelling. Future research will focus on extending subspace logic to non-linear inverse problems and developing adaptive, automated parameter-tuning strategies.
Summary updated