Compressive Sensing (CS) has long promised a revolutionary way to acquire signals: sample below the Nyquist rate by exploiting the underlying sparsity of a signal, and reconstruct the full data later via optimization. However, traditional CS faces a severe scalability bottleneck.
In a standard global CS framework, a high-dimensional signal $x \in \mathbb{R}^N$ is multiplied by a dense random sensing matrix $\Phi$. When dealing with large-scale data like high-definition video or megapixel images, $N$ becomes massive. Storing a global sensing matrix requires prohibitive amounts of memory, and the computational complexity of solving the resulting optimization problem scales as a high-order polynomial of $N$.
To bridge the gap between theoretical promise and real-time application, a powerful paradigm has emerged: Parallelized Compressive Sensing. The core intuition is to decouple a massive, ill-conditioned global problem into a collection of small, localized, and independent sub-problems. By restructuring both the physical acquisition hardware and the mathematical recovery algorithms, this approach shifts the computational bottleneck from monolithic matrix operations to distributed, parallel processing units.
The Mathematics of Spatial Decoupling
The fundamental trick to parallelizing CS is to enforce structure on the sensing matrix $\Phi$ so that it acts on localized segments of the signal independently. Instead of a dense, fully random matrix, researchers utilize block-diagonal or structurally constrained matrices.
As demonstrated by Rajaei et al. in the context of high-dimensional phase retrieval, partitioning a signal of size $N$ into $K$ non-overlapping sub-vectors allows a global reconstruction problem to be decomposed into independent sub-problems. This mathematical decoupling shifts the total time complexity from a high-order polynomial of the full signal size to the complexity of the smaller individual blocks, requiring only a low-dimensional global coordination step.
Global Sensing (Dense, Monolithic):
[ y ] = [ Dense Random Matrix ] * [ High-Dim Signal x ]
Parallelized Sensing (Block-Diagonal):
[ y1 ] [ \Phi_1 ] [ Block 1 ]
[ y2 ] = [ \Phi_2 ] * [ Block 2 ]
[ y3 ] [ \Phi_3 ] [ Block 3 ]
(Independent, Parallel Channels)
To make this practical for real-time streaming, Thong et al. introduced Structurally Random Matrices (SRMs). By combining simple pre-randomization with fast transforms (like the FFT or DCT) applied to localized segments via block-diagonal structures, the authors created sensing matrices that match the theoretical performance of purely random matrices while eliminating the need to buffer the entire signal or store a global matrix.
For multi-dimensional signals, this decoupling can also be performed column-by-column. Fang et al. proposed a column-wise sampling framework that applies a smaller sensing matrix to each column of a 2D signal independently. By pairing this with a strategic permutation step to distribute the signal's energy evenly, the authors relaxed the strict mathematical requirements of the Restricted Isometry Property (RIP) while enabling simultaneous encoding and decoding across parallel processing units.
Redesigning Hardware for One-Shot Parallel Acquisition
The benefits of spatial decoupling extend directly into physical optical architectures. Traditional single-pixel cameras capture measurements sequentially over time, creating a severe temporal bottleneck that prevents high-speed imaging. Parallelized CS architectures redesign the optical path to act as an array of independent detectors.
One approach is to distribute the compressive sensing workload across low-resolution sensor arrays. Chen et al. developed the FPA-CS architecture, where each individual pixel in a low-resolution focal plane array functions as an independent detector for a specific spatial sub-region. This setup effectively mimics thousands of single-pixel cameras operating in parallel, overcoming mechanical throughput limits and enabling high-resolution video capture at high frame rates. Similarly, Yuan et al. (2017) demonstrated a block-wise lensless camera that uses an array of discrete sensors to capture small image patches simultaneously, reducing computational complexity exponentially compared to global optical reconstruction.
Traditional Single-Pixel: [Scene] ---> [Single Photodetector] (Sequential over time)
Parallelized Array: [Scene] ---> [ Low-Res Sensor Array ] ---> [Parallel Patches]
(Each pixel acts independently)
Other architectures leverage dimensionality reduction through 1D sensor arrays or optical blurring:
- Linear Arrays: To capture high-resolution video in wavebands where 2D sensor arrays are prohibitively expensive, Wang et al. introduced LiSens. This architecture utilizes a 1D linear sensor array to capture coded line-integrals. By leveraging the spatial resolution of the line sensor, the system parallelizes the acquisition process and achieves megahertz measurement rates, bypassing the physical switching speed limitations of digital micromirror devices (DMDs).
- Unfocused Projections: Magli et al. designed a one-shot parallel compressive imaging architecture that projects an unfocused version of a scene onto a modulator. This spatial shifting ensures that different regions of a detector array capture unique, shifted copies of the image interacting with a fixed sensing mask, allowing for parallelized data acquisition in a single shot.
Distributing the Reconstruction Workload
Once a signal is captured via a spatially decoupled or block-diagonal hardware system, the mathematical reconstruction can likewise be distributed.
In Snapshot Compressive Imaging (SCI)—where multiple video frames are compressed into a single 2D snapshot—spatial decoupling plays a crucial role in scalability. As reviewed by Yuan et al. (2021), ensuring a localized relationship between the captured measurement and the original signal allows reconstruction algorithms to operate on small data patches in parallel. This property allows high-dimensional imaging systems to scale to larger resolutions by breaking down a massive global optimization problem into independent, localized computational tasks.
This algorithmic decoupling is highly flexible. For example, Yuan et al. (2021) demonstrated a "Plug-and-Play" (PnP) framework for video SCI that decouples the physical imaging model from the signal prior. By treating spatial regions independently during specific stages of the algorithm, the workload is easily parallelized across multiple GPUs, enabling ultra-high-definition video reconstruction up to 1000x faster than traditional iterative methods.
This divide-and-conquer strategy manifests across various domains:
- Medical Imaging: In dynamic parallel MRI, Bilen et al. showed that the mathematical structure of Cartesian sampling allows massive reconstruction problems to be decomposed into small, parallelizable tasks, enabling high-speed processing of dynamic data on GPUs.
- Hyperspectral Imaging: Arberet et al. integrated the pseudo-inverse of a known material mixing matrix into the sampling process. This step transforms a large, coupled optimization problem into smaller parallelizable tasks, achieving a 40-fold reduction in processing time for hyperspectral source separation.
- Distributed Learning: Beyond imaging, Jeon et al. applied this concept to federated learning over wireless channels, decomposing large-scale gradient reconstruction into parallel, small-scale sub-problems to enable the real-time processing of updates containing millions of parameters.
Deep Learning and Structural Rearrangements
The rise of deep learning has further accelerated parallelized compressive sensing. Instead of running slow, iterative optimization loops on individual blocks, researchers train neural networks to learn the direct mapping from compressed measurements to reconstructed signal patches.
Kulkarni et al. introduced ReconNet, a framework that divides a large image into smaller, non-overlapping blocks for independent sensing and reconstruction. By reducing the complexity of the learned mapping, this block-wise strategy allows for smaller, lightweight convolutional neural network architectures that process signal components entirely in parallel, yielding recovery speeds orders of magnitude faster than classical iterative approaches.
Block-Wise Deep Recovery:
[ Compressed Measurements ] ---> [ Parallel Network Channels ] ---> [ Reconstructed Patches ] ---> [ Final Signal ]
To optimize the sensing operation itself within deep networks, Mousavi et al. demonstrated that large-scale strided convolutions used for signal sensing can be mathematically rearranged into multiple smaller, parallel convolutions. This structural rearrangement reduces the computational complexity of the forward pass from quadratic to linear relative to the number of measurements ($O(MN)$ to $O(M)$), unlocking real-time signal recovery.
Even when dealing with highly distorted or quantized data, parallel matrix structures offer a computational lifeline. For sparse signal recovery from noisy 1-bit binary measurements, Yang et al. utilized extended matrices and Hadamard products within a deep unfolded network. This architectural choice allows for the parallel processing of multiple signal vectors simultaneously, bypassing the need to diagonalize measurement vectors for each individual sample and dropping the reconstruction complexity from cubic to quadratic time.
By aligning the physical physics of sampling with block-structured linear algebra, parallelized compressive sensing bypasses the curse of dimensionality, turning what was once a computationally prohibitive optimization problem into a highly scalable, real-time technology.
Key Foundational Work
Non-Cancellation Multistage Kurtosis Maximization with Prewhitening for Blind Source Separation (2009) — contributed 1 concept elements to this direction.
Fast and Efficient Compressive Sensing Using Structurally Random Matrices (2011) — contributed 1 concept elements to this direction.