In compressed sensing and sparse recovery, the goal is to reconstruct a high-dimensional sparse signal from a limited number of linear measurements. The boundary that dictates whether an algorithm can successfully recover a signal is known as the phase transition. Traditionally, this framework was evaluated using real-valued signals and matrices. However, when we extend sparse recovery into the complex domain, a remarkable phenomenon occurs: the phase transition boundary shifts dramatically upward, allowing for the flawless reconstruction of signals that are significantly denser, or using far fewer measurements, than would be possible in the real domain.
To understand why this happens, we must look past the surface-level algebra and examine the structural constraints that the complex domain naturally imposes on data.
The Mechanism: Implicit Joint Sparsity
The fundamental advantage of complex-valued signal recovery stems from a property known as implicit joint sparsity.
Consider a sparse complex vector. For any given element $z = x + iy$ to be zero, both its real part $x$ and its imaginary part $y$ must simultaneously equal zero. Conversely, if an element is non-zero, its energy is typically distributed across both its real and imaginary components. Crucially, this means that the real and imaginary parts of the signal are not independent; they share the exact same support set (the locations of the non-zero entries).
As Yang et al. demonstrate in On Phase Transition of Compressed Sensing in the Complex Domain, this structural constraint allows us to reformulate a complex recovery problem into a block-sparse framework with a block size of two. Instead of searching for a sparse vector in a vacuum, the recovery algorithm leverages the fact that the real and imaginary components provide two coupled views of the same underlying sparsity pattern. This implicit coupling simplifies the optimization landscape and expands the regime where signal reconstruction succeeds.
Equivalence to Multi-Measurement Vector Problems
This coupling can be formalized by mapping the problem to a well-known framework in signal processing: the Multi-Measurement Vector (MMV) problem. In an MMV problem, an algorithm attempts to recover multiple distinct measurement vectors that are known to share a common support matrix.
In Performance Limits for Noisy Multimeasurement Vector Problems, Zhu et al. establish that complex-valued compressed sensing is mathematically equivalent to an MMV problem where the real and imaginary components act as two distinct vectors sharing a single support. By treating the components jointly rather than independently, algorithms can pool information from both channels to identify the true support of the signal much more reliably.
Independent Real Recovery (Less Information per Element):
Real Part: [ X , 0 , 0 , X , 0 ] -> Support: {1, 4}
Imaginary Part: [ 0 , 0 , 0 , Y , Y ] -> Support: {4, 5}
Joint Complex Recovery (Shared Support Constraint):
Complex Signal: [ Z , 0 , 0 , Z , 0 ] -> Joint Support: {1, 4}
When algorithms are designed to natively exploit this joint processing, the performance gains are substantial. For example, Anitori et al. developed the Complex Approximate Message Passing (CAMP) algorithm in Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP). Through a precise state evolution analysis, the authors proved that in highly undersampled regimes, complex LASSO can successfully recover signals that are twice as dense as those recoverable by standard real-valued LASSO.
Algorithmic Gaps and Practical Applications
The theoretical advantage of the complex domain only manifests if the reconstruction algorithm is explicitly designed to respect this structural correlation. As Huang et al. point out in A Class of Deterministic Sensing Matrices and Their Application in Harmonic Detection, standard greedy recovery algorithms often fail in practice because they treat real and imaginary parts as independent variables. When moving from complex-domain theory to real-valued hardware implementations, optimization routines must be specifically tailored to target this linked structural sparsity to avoid losing the phase transition advantage.
When properly harnessed, this joint sparsity constraint solves difficult engineering problems in physical domains where signals are inherently complex-valued:
- Power Grid Topology: In power systems, identifying the network structure requires estimating a complex-valued Laplacian matrix. In Estimation of Complex-Valued Laplacian Matrices for Topology Identification in Power Systems, Halihal et al. demonstrate that the real and imaginary parts of the admittance matrix share identical zero locations. By enforcing a joint sparsity constraint via an Alternating Direction Method of Multipliers (ADMM) framework, the authors achieved highly accurate topology recovery even under non-linear power flow conditions.
- Phase Retrieval: The benefits of the complex domain extend even to non-linear problems like phase retrieval, where phase information is entirely lost during measurement. In Phase retrieval in high dimensions: Statistical and computational phase transitions, Maillard et al. analyzed the statistical physics of high-dimensional phase retrieval. The authors found that complex-valued signals exhibit a significantly smaller gap between theoretical (information-theoretic) limits and algorithmic recovery limits than real-valued signals. The additional degrees of freedom and implicit constraints inherent in the complex domain fundamentally ease the path to algorithmic convergence.
Ultimately, treating complex signals as unified entities rather than pairs of independent real vectors changes the geometry of the sparse recovery problem. By leveraging the implicit joint sparsity of the real and imaginary components, researchers can push past traditional limits of compressed sensing, achieving robust reconstruction in highly undersampled regimes.
Key Foundational Work
On Phase Transition of Compressed Sensing in the Complex Domain (2011) — contributed 5 concept elements to this direction.
Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP) (2013) — contributed 2 concept elements to this direction.