High-dimensional signal recovery frameworks like compressed sensing and phase retrieval offer powerful theoretical guarantees: they allow us to reconstruct a signal from far fewer measurements than its ambient dimension suggests. However, translating this theory into practice hits a severe computational wall. Traditional global optimization algorithms—such as semidefinite programming or joint basis pursuit—often scale quadratically ($O(N^2)$) or cubically ($O(N^3)$) with the number of signal samples $N$. For high-resolution 2D images, 3D hyperspectral cubes, or massive sensor arrays, this polynomial complexity quickly becomes mathematically intractable, exhausting both memory and time.
To bypass this scaling wall, a prominent research direction focuses on structural decomposition. Instead of solving a massive global optimization problem all at once, these approaches break the problem down into smaller, parallelizable, or hierarchical sub-problems, or exploit the intrinsic mathematical structure of the measurement operators to achieve near-linear or sublinear runtimes.
Pruning the Search Space with Multi-Stage Recovery
One powerful intuition for scaling recovery is to avoid running expensive optimization algorithms over the entire high-dimensional ambient space. Because sparse signals are mostly composed of zero-valued coefficients, we can use a fast, coarse first pass to isolate the signal's true support, and then apply high-fidelity reconstruction only where it matters.
For example, in Two-Part Reconstruction in Compressed Sensing and Two-Part Reconstruction with Noisy-Sudocodes, Yanting Ma et al. introduce a "divide and conquer" framework. Their approach uses a lightning-fast first pass to identify and prune zero-valued coefficients. By shrinking the problem size upfront, a heavier, standard compressed sensing algorithm can efficiently finish the job on a fraction of the original variables. This turns a massive global optimization problem into a highly manageable local one.
Taking this hierarchical view further, Yanbin He et al. propose a Multi-Stage Recovery (MSR) framework in Hierarchical Multi-Stage Recovery Framework for Kronecker Compressed Sensing. By reinterpreting high-dimensional Kronecker compressed sensing as a sequence of smaller, nested sub-problems, the authors achieve state-of-the-art accuracy while running up to three orders of magnitude faster than traditional joint-reconstruction techniques.
Divide and Parallelize via Block-Based Localization
Another strategy to break the polynomial complexity curve is spatial or structural localization. If an algorithm scales cubically, splitting a signal of size $N$ into $B$ independent blocks of size $N/B$ reduces the total computational cost from $O(N^3)$ to:
$$B \times O\left(\left(\frac{N}{B}\right)^3\right) = O\left(\frac{N^3}{B^2}\right)$$
This block-based decomposition is highly effective in phase retrieval—recovering a signal from only the magnitude of its measurements—which is notoriously expensive. In Fast Phase Retrieval for High Dimensions: A Block-Based Approach, Boshra Rajaei et al. break a massive phase retrieval problem into smaller, parallelizable sub-problems, drastically reducing memory overhead and accelerating recovery by several orders of magnitude.
Similarly, Mark A. Iwen et al. introduce BlockPR in Fast Phase Retrieval from Local Correlation Measurements. By exploiting the block-circulant structure of "lifted" local measurements, the authors achieve a near-linear runtime of $O(d \log^4 d)$, bypassing the traditional $O(d^3)$ complexity wall entirely.
Predictive and Low-Rank Structural Shortcuts
Beyond physical blocks, we can exploit the intrinsic mathematical structures of the measurement operators and the signals themselves to avoid explicit high-dimensional computations.
In multidimensional signal acquisition, Giulio Coluccia et al. demonstrate in Progressive Compressed Sensing and Reconstruction of Multidimensional Signals Using Hybrid Transform/Prediction Sparsity Model that combining transform-based sparsity with an iterative inter-dimension prediction model allows high-quality reconstruction at a fraction of the cost of joint global methods. In a similar vein, Giulio Coluccia et al. show in A Novel Progressive Image Scanning and Reconstruction Scheme based on Compressed Sensing and Linear Prediction that iteratively predicting rows from their neighbors and reconstructing only the remaining "prediction error" makes high-resolution processing mathematically tractable in memory-limited environments.
Furthermore, optimization algorithms often require global parameters that are expensive to compute. Anders Holst et al. tackle this in Computing the Lipschitz Constant Needed for Fast Scene Recovery from CASSI Measurements by proving that the Lipschitz constant needed for optimal step sizes can be calculated from a tiny snapshot matrix rather than a massive measurement matrix, removing a major computational bottleneck.
Finally, when recovering structured signals from data corrupted by outliers, Jian-Feng Cai et al. (Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery) avoid expensive semidefinite programming by combining the low-rank properties of Hankel matrices with non-convex tangent space projections, achieving a 10x speedup with a provable linear convergence rate. For multi-vector problems, Hongtao Lu (A Fast Algorithm for Recovery of Jointly Sparse Vectors based on the Alternating Direction Methods) avoids expensive second-order derivatives or complex projections by applying the Alternating Direction Method directly to matrix norm minimization, achieving massive speedups over previous solvers.
By shifting from global, brute-force optimization to localized, multi-stage, and structurally aware algorithms, these approaches collectively demonstrate that high-dimensional signal recovery can scale efficiently without sacrificing mathematical rigor or reconstruction fidelity.
Key Foundational Work
Bayesian Modeling and Classification of Neural Signals (1993) — contributed 1 concept elements to this direction.
Random Filters for Compressive Sampling and Reconstruction (2006) — contributed 1 concept elements to this direction.