In classical compressed sensing, we assume we can observe a sparse signal $x$ through a perfectly known linear lens, modeled as $y = Ax + n$, where $A$ is the sensing matrix and $n$ is additive noise. This elegant formulation underpins foundational guarantees, such as those established by Candès in Exact Matrix Completion via Convex Optimization.
However, real-world hardware is rarely perfect. Lens aberrations, sensor miscalibrations, thermal fluctuations, and discretization jitter mean that the matrix we think we are using ($\hat{A}$) deviates from the physical matrix ($A$) that actually modulated the signal. As Herman et al. point out in General Deviants: An Analysis of Perturbations in Compressed Sensing, this creates a "completely perturbed" scenario where errors corrupt both the measurements and the operator itself.
The Multiplicative Noise Floor
Why does this matrix mismatch matter so much? Let's look at the math. If we model the true sensing matrix as $A = \hat{A} - E$, where $E$ is an unknown perturbation matrix, our measurement equation becomes:
$$y = (\hat{A} - E)x + n = \hat{A}x + (n - Ex)$$
When we run a standard reconstruction algorithm using our assumed matrix $\hat{A}$, the algorithm treats the entire term $(n - Ex)$ as the noise vector.
This reveals a fundamental asymmetry. While $n$ is simple additive noise, the term $Ex$ is multiplicative—it scales directly with the magnitude of the unknown signal $x$. As noted by Zhu et al. in Maximum Likelihood Estimation From Sign Measurements With Sensing Matrix Perturbation, this drastically complicates recovery. Even if we completely eliminate external measurement noise ($n = 0$), the effective noise $-Ex$ remains. This creates a persistent error floor: the signal cannot be perfectly reconstructed no matter how clean the environment is, a phenomenon detailed by Yang et al. in Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation.
Exploiting Structure in the Chaos
If the perturbation $E$ were completely arbitrary, recovery would be hopeless. Fortunately, physical hardware imperfections usually follow specific structural patterns.
For instance, in sensor arrays used for Direction of Arrival (DOA) estimation, hardware errors often manifest as uncompensated sensor gains or phase shifts. Yang et al. exploit this by decomposing the perturbation into a known directional matrix and an unknown diagonal matrix of magnitudes, allowing the system to treat the perturbation as an additional signal component to be recovered. Similarly, Wang et al. demonstrate in DOA estimation of coherently distributed sources based on block-sparse constraint with measurement matrix uncertainty that integrating an explicit bound for matrix uncertainty directly into the optimization objective stabilizes the recovery process against basis mismatch.
In medical imaging applications like MRI or CT, hardware jitter often shifts the expected sampling frequencies. Malhotra et al. address this in Signal Recovery in Perturbed Fourier Compressed Sensing by estimating these frequency shifts in situ alongside the signal using alternating minimization.
Total Least-Squares and Blind Calibration
When we acknowledge that both the observation vector $y$ and the design matrix $\hat{A}$ are noisy, standard least-squares objectives fail. A more natural framework is Total Least-Squares (TLS), which minimizes errors in both components simultaneously.
The authors of Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling (Zhu et al.) introduced Sparse Total Least-Squares (S-TLS) to bridge this gap, providing a robust optimization framework for dual-source errors.
When multiple independent signals are captured through the same imperfect hardware, the problem transitions into blind calibration or bilinear recovery. Because the perturbation is shared across measurements, we can leverage the collective data to solve for both the signals and the hardware parameters. Bilen et al. developed convex optimization approaches for this task in Convex Optimization Approaches for Blind Sensor Calibration using Sparsity.
To make this computationally viable for large-scale systems, Schülke et al. introduced Cal-AMP, a message-passing algorithm that calibrates sensors on-the-fly. Further advancing this direction, Fletcher et al. proposed BAd-VAMP in Bilinear Recovery using Adaptive Vector-AMP, bypassing memory-intensive matrix lifting techniques to jointly estimate signals and system parameters efficiently.
Do Standard Algorithms Gracefully Degrade?
An important theoretical question is whether standard, uncalibrated sparse recovery algorithms completely collapse under matrix uncertainty, or if they degrade gracefully.
Herman demonstrated in General Perturbations in Compressed Sensing that stable signal recovery remains possible even under complete perturbations, with performance bounded by the total noise level. For greedy algorithms, Chen et al. proved in Oracle-Order Recovery Performance of Greedy Pursuits With Replacement Against General Perturbations that methods like CoSaMP and Subspace Pursuit achieve "oracle-order" performance—meaning their error scales predictably, mirroring a scenario where the support was known beforehand.
Furthermore, Ding et al. and Ding et al. provided rigorous proofs showing that Orthogonal Matching Pursuit (OMP) can still perfectly recover the underlying support set of a signal under matrix perturbations, provided the matrix satisfies certain Restricted Isometry Property (RIP) conditions.
The Modern Frontier: Learning the Residuals
As sensing systems grow more complex, explicitly modeling every physical perturbation becomes intractable. Modern researchers are turning to deep learning and deep unfolding to handle hardware model mismatches implicitly.
In Residual Degradation Learning Unfolding Framework with Mixing Priors Across Spectral and Spatial for Compressive Spectral Imaging, Dong et al. introduced a framework that explicitly learns the "residual" physical errors of hardware (such as lens aberrations) rather than assuming an idealized forward model. In an even more radical shift, Khobahi et al. demonstrated in One-Bit Compressive Sensing: Can We Go Deep and Blind? that deep-unfolded networks can perform "blind" recovery from 1-bit measurements without any prior knowledge of the sensing matrix, adapting dynamically to environmental noise and calibration errors that would otherwise break classical algorithms.
Key Foundational Work
General Deviants: An Analysis of Perturbations in Compressed Sensing (2009) — contributed 2 concept elements to this direction.
General Perturbations in Compressed Sensing (2009) — contributed 2 concept elements to this direction.
Exact Matrix Completion via Convex Optimization (2008) — contributed 1 concept elements to this direction.