Source-linked AI summary
General Deviants: An Analysis of Perturbations in Compressed Sensing
Matthew A. Herman, Thomas Strohmer
TL;DR
The paper studies Basis Pursuit when both observations and the sensing matrix are perturbed, addressing matrix perturbations omitted by earlier partially perturbed models. It develops a completely perturbed framework and shows that, under suitable conditions, recovery stability is limited by observation noise and is comparable to oracle least squares, while simulations show linear error scaling with relative perturbation.
Problem
Earlier compressed sensing studies considered additive observation noise but had scarcely analyzed perturbations E to the measurement matrix A.
Method
The paper develops a Basis Pursuit analysis for a completely perturbed model containing both additive noise e and matrix perturbations E.
Results
Under suitable conditions, Basis Pursuit stability is limited by total observation noise and can be compared with the oracle least squares solution; simulations show error scaling linearly with εA.
Takeaways & Limitations
The framework extends stable compressed sensing recovery analysis to multiplicative matrix noise and supports comparison with best-case oracle least squares reconstruction.
Takeaways & Limitations
The analysis generally assumes no specific knowledge of E and e, so their relative upper bounds must be calculated or estimated carefully.
Abstract
from arXiv · showhide
We analyze the Basis Pursuit recovery of signals with general perturbations. Previous studies have only considered partially perturbed observations Ax + e. Here, x is a signal which we wish to recover, A is a full-rank matrix with more columns than rows, and e is simple additive noise. Our model also incorporates perturbations E to the matrix A which result in multiplicative noise. This completely perturbed framework extends the prior work of Candes, Romberg and Tao on stable signal recovery from incomplete and inaccurate measurements. Our results show that, under suitable conditions, the stability of the recovered signal is limited by the noise level in the observation. Moreover, this accuracy is within a constant multiple of the best-case reconstruction using the technique of least squares. In the absence of additive noise numerical simulations essentially confirm that this error is a linear function of the relative perturbation.
I. INTRODUCTION
Compressed sensing recovery is extended from additive observation noise to perturbations in the sensing matrix itself. The paper motivates this model, states its assumptions, and situates Basis Pursuit within prior stability analyses.
- Signal and measurement model: Signals are modeled as sparse or compressible vectors measured by a full-rank matrix A with m ≤ n.K-sparse vectors have at most K nonzero entries; compressible vectors have coefficients that decay according to a power law.
- Prior model: Prior compressed sensing work considered additive noise e in the observations, which typically represents errors uncorrelated with the signal.The partially perturbed model is written as ˆb = Ax + e.
- General perturbations: The paper addresses largely unstudied perturbations E to the sensing matrix by using ˆA = A + E, thereby modeling multiplicative noise.Such perturbations are harder to analyze because they are correlated with the signal and produce an additional Ex term.
- Motivation: Matrix perturbations matter for precision errors in implemented sensors, inaccurate transmission-channel assumptions, and distortions from analog-signal discretization.Examples include radar, remote sensing, telecommunications, source separation, jitter error, and overly coarse sampling periods.
- Assumptions and analysis: The analysis quantifies perturbations through relative upper bounds and examines Basis Pursuit under restricted-isometry and related matrix conditions.The framework assumes relative perturbation bounds below 1 and builds on prior stability results for the partially perturbed case.
B. Incorporating nontrivial perturbation E
The paper extends Basis Pursuit analysis to simultaneously perturbed sensing matrices and observations, deriving RIP and recovery guarantees under suitable conditions. The perturbation bounds are worst-case, and numerical examples show that matrix perturbations worsen the resulting stability constants.
- Model and guarantees: The completely perturbed Basis Pursuit problem incorporates a distinct decoding matrix ˆA when both matrix perturbations E and additive noise e are present.This extends the partially perturbed formulation to account for multiplicative and additive noise together.
- Model and guarantees: Theorem 1 bounds the restricted isometry constant of ˆA using the original matrix A and the relative perturbation in its K-column submatrices.The resulting ˆδK is bounded above by ˆδK,max.
- Interpretation and limitations: The perturbation bound is worst-case because only a worst-case relative perturbation is assumed; distinct nonzero perturbations can nevertheless leave ˆδK unchanged.A unitary transformation ˆA = AU provides an example with E ≠ 0 and ˆδK = δK.
- Model and guarantees: Under its RIC, signal, and perturbation assumptions, Theorem 2 guarantees a stable BP solution with an error bound determined by the total noise parameter.For K-sparse signals, the terms associated with the tail xKc vanish, simplifying the accuracy expression.
- Relation to prior work: When E = 0, the perturbed framework reduces to the corresponding Candès assumptions and constants for additive-noise recovery.The RIPs for A and ˆA coincide, and the additional perturbation condition is no longer needed.
- Numerical implications: Numerical examples show that perturbations to A increase the BP stability constants C0 and C1, although these examples represent worst-case instances.For δ2K = 0.100 and ε(2K)A = 5%, the reported constants are C0 = 4.47 and C1 = 9.06, compared with 2.75 and 5.53 without perturbation.
C. Numerical Simulations
The simulations generate perturbed Gaussian sensing matrices and show that Basis Pursuit relative error scales roughly linearly with matrix perturbation. They also note that support-based least-squares refinement could improve recovery but is not analyzed.
- 128 × 512 Gaussian matrices were tested over 100 trials with εA ∈ {0, 0.01, 0.05, 0.1}, scaling each perturbation to the chosen spectral-norm level.The simulations used normally distributed entries and εb = 0.
- At K = 10, relative errors for εA = 0.01, 0.05, 0.1 were 9.7×10−3, 4.9×10−2, and 9.7×10−2, respectively.The latter two errors are approximately five and ten times the first.
- Across fixed K ≤ 30, the observed relative error scales roughly linearly with εA, confirming the corresponding conclusion of Theorem 2.
- Using Basis Pursuit only to determine support followed by least squares could improve theoretical and simulated performance, but this recovery method is outside the present analysis.
A. Proof of Theorem 1
The proof of Theorem 1 bounds the restricted isometry behavior of the perturbed matrix using the original matrix’s RIC and relative perturbation. The bound is designed as a sharp worst-case estimate under the perturbation model.
- The proof defines lower and upper perturbation bounds for K-column submatrices of the perturbed matrix from δK and ε(K)A.
- The simulations associated with Figure 1 average BP relative error over 100 trials against sparsity K for several εA values with εb = 0.
- The inequalities are sharp because equality can occur when E is a positive real multiple of A, while the original RIP upper bound is itself sharp.
- The resulting perturbed RIC ˆδK is the smallest nonnegative symmetric constant covering those bounds.
B. Bounding the perturbed observation
This section bounds the combined effect of matrix and observation perturbations without requiring the exact perturbation or signal. The bound separates multiplicative and additive noise contributions and supports the subsequent recovery analysis.
- A lower bound for Ax is established from the head and tail of a general signal together with the RIC of A.
- The analysis seeks an upper bound on total perturbation using relative perturbation levels, removing dependence on the unknown input signal x.
- The total perturbation bound combines the contribution from matrix perturbation E with additive noise e.
- The results can be expressed using the perturbed observation by substituting ∥b∥2 ≤ ∥ˆb∥2(1 − εb)−1.
C. Proof of Theorem 2
The proof of Theorem 2 adapts the Basis Pursuit stability argument to the perturbed decoding matrix. It controls the recovery error through the perturbed matrix’s RIP and verifies the denominator condition required for finite constants.
- The BP minimizer is written as z⋆ = x + h, where h is the perturbation from the true solution induced by E and e.
- The proof replaces the decoding matrix A with ˆA and bounds the image of h using the BP constraint and feasibility of x.
- The argument yields perturbed stability constants ˆα and ˆρ in place of the original α and ρ.
- Finite recovery bounds require 0 < 1 − ˆρ, and the theorem’s hypothesis is shown to imply this condition through the perturbed RIC bound.
D. Proof of Lemma 1
The proof establishes the lemma through successive implications from the theorem’s assumption, selecting k = 2K and then extending the result to all k ≤ 2K.
- Assumption (12) implies the intermediate inequality required by the proof.
- Algebraic manipulation then confirms the next stated relation.
- k = 2K establishes (18), and the result also holds for every k ≤ 2K.
- The resulting bound on min(A) proves the lemma’s first part, while the second part follows immediately.
IV. CLASSICAL ℓ2 PERTURBATION ANALYSIS
The least-squares analysis assumes known support for the best K-sparse approximation, derives a stability expression under perturbations, and bounds the reconstruction error by approximation error plus perturbation noise.
- AT denotes the submatrix formed by columns indexed by T, while xT contains the corresponding coefficients.
- The analysis restricts attention to a K-element support T, with AT full rank because K ≤ m.
- Knowing T permits solving the perturbed least-squares problem and zero-padding its coefficients outside T.
- The perturbation assumption is used to support the least-squares comparison and does not constrain compressed-sensing recovery or Basis Pursuit.
- The derived stability bound has the form ∥z# − x∥2 ≤ ∥x − xK∥2 + C2ζ′.
A. Comparison of LS with BP
The comparison treats oracle least squares as a best-case benchmark against Basis Pursuit, finding that both methods’ accuracy is governed by observation noise while perturbation effects scale linearly in simulations.
- A fair LS–BP comparison requires strictly K-sparse signals because LS is strictly K-sparse whereas BP generally is not.
- The least-squares analysis is oracle and best-case, whereas BP represents a worst-case recovery scenario for comparison purposes.
- Both BP and least squares achieve accuracy on the order of the noise level in the perturbed observation.
- The framework extends earlier additive-noise analysis by incorporating multiplicative noise from perturbations to the sensing matrix.
- The study uses worst-case relative perturbation measures that must be calculated or estimated carefully in applications.
- The perturbed matrix’s K-column spectral penalty varies linearly with relative perturbation, and simulations confirm linear BP-error scaling without additive noise.
- Known RIP-satisfying matrices remain limited essentially to random Gaussian, Bernoulli, and certain partial unitary matrices.
APPENDIX
The appendix distinguishes random and structured perturbations and explains how knowledge of their structure can sharpen bounds on perturbation effects.
- Random and structured perturbations are the two principal classes considered, and their nature affects ∥E∥(K)A.
- Without structural knowledge, the analysis can use a worst-case upper bound based on the full matrix spectral norm.
- For E = βR with 0 < β ≪ 1, the RIP of a random matrix R provides a route to analyzing E.
- For structured perturbations such as partial circulant matrices, their construction may enable tighter bounds on ∥E∥(K)A.
- The appendix points readers to related literature on these perturbation structures.