Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation

Zai Yang; Cishen Zhang; Lihua Xie

Source-linked AI summary

Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation

Zai Yang, Cishen Zhang, Lihua Xie

arXiv:1112.0071v2Dec 1, 2011cs.IT

TL;DR

The paper addresses compressed sensing when the sensing matrix is affected by structured, unknown perturbations. It incorporates the perturbation structure into ℓ1 minimization and establishes recovery guarantees, including exact noise-free recovery under suitable sparsity and perturbation conditions. Algorithms and simulations support the analysis, with an application to direction-of-arrival estimation.

Problem
Standard compressed sensing assumes the sensing matrix is known a priori, an assumption that may fail when sensing instruments introduce structured errors or fluctuations.
Method
The paper models structured perturbations through known column directions with unknown coefficients and incorporates this structure into an ℓ1 minimization problem.
Results
The method achieves robustly stable sparse-signal recovery with error proportional to measurement noise; for δ̄4k(Ψ) = 0.2, the bounds are 8.48ϵ, 8.50ϵ, and 11.0ϵ for r = 0.01, 0.1, and 1, respectively.
Takeaways & Limitations
Structured perturbation information can preserve noise-level recovery behavior, support exact recovery in the noise-free sufficiently sparse case, and apply to DOA estimation.

Abstract

from arXiv · show

The sparse signal recovery in the standard compressed sensing (CS) problem requires that the sensing matrix be known a priori. Such an ideal assumption may not be met in practical applications where various errors and fluctuations exist in the sensing instruments. This paper considers the problem of compressed sensing subject to a structured perturbation in the sensing matrix. Under mild conditions, it is shown that a sparse signal can be recovered by $\ell_1$ minimization and the recovery error is at most proportional to the measurement noise level, which is similar to the standard CS result. In the special noise free case, the recovery is exact provided that the signal is sufficiently sparse with respect to the perturbation level. The formulated structured sensing matrix perturbation is applicable to the direction of arrival estimation problem, so has practical relevance. Algorithms are proposed to implement the $\ell_1$ minimization problem and numerical simulations are carried out to verify the result obtained.

I. INTRODUCTION

Standard compressed sensing assumes the sensing matrix is known, but practical errors can perturb that matrix. This paper studies structured perturbations and develops recovery guarantees, optimization insights, and numerical validation.

Motivation: Standard CS recovers sparse or compressible signals from noisy measurements using ℓ1 minimization under mild sensing-matrix conditions.The recovery error is proportional to the measurement-noise level.
Motivation: In practical settings, sensing matrices may be inaccurate because of quantization, estimation error, or discretization in source localization and radar imaging.These applications include direction-of-arrival estimation with discretized continuous parameters.
Structured perturbation: The paper models each perturbation column as an unknown scalar times a known direction vector and seeks recovery guarantees under this structure.The structured model supports robustly stable recovery under conditions similar to standard CS.
Main guarantees: Robustly stable recovery bounds the reconstruction error proportionally to measurement noise, while noise-free recovery is exact for sufficiently sparse signals relative to perturbation.The paper also reports an analogous result for compressible signals under an additional assumption.
Optimization perspective: The paper characterizes optimization solutions that can estimate the signal accurately without being globally optimal, aiding assessment of algorithms such as nonconvex ℓp minimization.This is relevant when algorithms cannot guarantee an optimal nonconvex solution.

B. Stable Signal Recovery of Standard CS

Standard CS uses RIP-based conditions to guarantee stable recovery through efficient ℓ1 optimization. With an unknown additive matrix perturbation, nominal-matrix recovery generally incurs perturbation-dependent error and requires a separate robustness analysis.

Standard CS: The standard CS task recovers the original signal from reduced noisy measurements using the known sensing matrix and an upper noise bound.The paper focuses on the ℓ1-norm minimization approach.
Standard CS: The restricted isometry property defines how nearly a sensing matrix preserves the norm of sparse vectors and supports recovery guarantees.A matrix satisfies the k-RIP when its restricted isometry constant is below 1.
Stable recovery: Under a suitable RIP condition, BPDN stably recovers sparse and compressible signals, with exact recovery for sparse signals in the noise-free case.For sparse signals, the relevant condition is stated using δ2k(Φ).
Perturbed CS: With true matrix Φ = A + E but only nominal matrix A known, the perturbation term Exo acts as signal-correlated noise and is harder to analyze than measurement noise.This motivates robust recovery guarantees for perturbed CS.
Perturbed CS: Nominal-matrix BPDN is robust to small perturbations, but its recovery error grows linearly with perturbation level and is generally not stable under the paper’s definition.The cited result applies to sparse signals and has related extensions for compressible signals.

III. SP-CS: CS SUBJECT TO STRUCTURED PERTURBATION

The paper models sensing-matrix errors through known perturbation directions and bounded unknown coefficients, then analyzes recovery using duplicate-RIP conditions and structured ℓ1 minimization. In the noiseless case, sufficiently sparse signals and perturbation parameters can be recovered exactly, while noisy recovery is robustly stable under stated conditions.

Problem formulation: The perturbation is modeled as E = B∆o, where B is known and each perturbation column follows a known direction with bounded coefficient βo ∈ [−r, r].The columns of B are assumed to have unit norm, and the observation model includes bounded measurement noise.
Problem formulation: A vector is 2k-duplicately sparse when its two same-dimensional components are each k-sparse and share the same support.The corresponding D-RIP is defined over these jointly sparse vectors for Ψ = [A, B].
Exact recovery: In the noise-free case, an optimal solution to the perturbed combinatorial problem recovers both xo and βo when ||xo||0 ≤ k and the 4k-D-RIC is below 1.The combinatorial formulation minimizes ||x||0 subject to the perturbed observation model.
Stable recovery: The P-BPDN formulation minimizes ||x||1 subject to a residual bound, incorporating the structured perturbation through A + B∆.This convex formulation is introduced because the combinatorial problem is computationally difficult and noise-sensitive.
Stable recovery: For k-sparse signals, robustly stable recovery has error at most proportional to the noise level when the D-RIC is sufficiently small relative to r.The perturbation coefficients are also stably recovered on the support of xo; the general-signal bound includes an additional perturbation-dependent term.
Scope: Robust stability generally cannot be concluded for compressible signals under large perturbations, although it holds under an additional small-perturbation assumption.The error-bound coefficient grows as C1 = O(r).

C. Interpretation of the Main Results

The main results show that structured perturbations can be incorporated into compressed-sensing recovery without losing noise-level error control under suitable D-RIP conditions. The interpretation compares this guarantee with standard CS, identifies when larger perturbations remain admissible, and clarifies limits for compressible signals and alternative formulations.

Theorem 4: Theorem 4 obtains noise-proportional recovery for k-sparse signals by ℓ1 minimization that incorporates the perturbation structure.The D-RIC must be sufficiently small relative to the perturbation level, and βo is stably recovered on the support of xo.
Theorem 4: Unlike the existing perturbed-CS result, the Theorem 4 error is constrained by measurement noise rather than acquiring an error term whenever perturbation appears.The result is described as similar to standard CS under its D-RIP condition.
Perturbation level: For a fixed Ψ with 4k-D-RIC 0.2, the perturbation level must satisfy the theorem-specific upper bound on r.The cited passage introduces this requirement but does not preserve the bound’s numeric value.
Perturbation level: The structured result can apply to larger perturbations when Ψ has sufficiently small D-RIC, whereas the existing result does not cover that regime.Thus, perturbation magnitude and the D-RIC jointly determine the applicable recovery regime.
General signals: Theorem 5 generalizes Theorem 4 to general signals, but robust stability does not generally hold for compressible signals under large perturbations.An additional assumption r = O(...) restores the stated robust-stability conclusion when the D-RIP condition is satisfied.
Connection to standard CS: As r → 0, the structured-perturbation conditions and error bounds coincide with standard CS, apart from the symbolic difference between the two RIP quantities.The D-RIP condition can also be satisfied under standard-CS-like random-matrix scaling in the high-dimensional, small-r regime.
Alternative formulation: The alternative TPS-BPDN formulation transforms the perturbation into a signal component but can require about twice as many measurements as P-BPDN in high-dimensional settings.For moderate perturbations, the P-BPDN D-RIP condition varies slowly and is weaker in the cited comparison.

E. Relaxation of the Optimal Solution

The paper shows that feasible, non-optimal solutions can still provide good recovery under the stated conditions. This relaxation supports algorithm assessment and has practical relevance for off-grid DOA estimation.

Relaxation of optimality: In standard CS, any feasible x inside the BPDN domain and ℓ1 ball is a good candidate for recovering xo.The triangular region in Fig. 1 represents the intersection of these two sets.
Relaxation of optimality: The optimal solution is sought because ∥xo∥1 is generally unavailable, making the required ℓ1-norm condition difficult to verify directly.This explains why optimality remains useful even though it is not necessary for the recovery guarantee.
Algorithm assessment: The relaxation provides a criterion for judging algorithms that return feasible, non-optimal solutions, including rONE-L1 and ℓp minimization methods.An algorithm is effective when its output is feasible and has ℓ1 norm no larger than that of the original signal.
DOA application: The structured perturbation framework applies to DOA estimation, where off-grid sources create modeling errors in a complex sensing model.The paper relates coarse-grid DOA estimation to structured matrix perturbation and notes that the recovery results extend to the complex case.

IV. ALGORITHMS FOR P-BPDN

The paper develops algorithms for the generally nonconvex P-BPDN problem, including a convex reformulation for positive signals and an alternating method for general signals. Theoretical results characterize feasible-domain behavior, stationarity, and convergence-related properties.

Positive signals: For positive signals, PP-BPDN is equivalent to the convex problem (P1), so an optimal PP-BPDN solution can be obtained efficiently through convex optimization.The equivalence uses the substitution p = β ⊙x.
General signals: For general signals, AA-P-BPDN alternates across a sequence of BPDN problems to address the nonconvex P-BPDN formulation.The algorithm is analyzed through the behavior of its iterates and associated feasible domains.
Feasible-domain analysis: If the sensing matrices converge, the corresponding feasible domains converge in the sense that points in the limiting domain can be approximated by points in the sequence of domains.Lemma 1 supplies the feasible-domain continuity property used in the analysis.
BPDN structure: An optimal BPDN solution is zero when ∥y∥2 ≤ϵ and otherwise lies on the boundary ∥y −Φx∗∥2 = ϵ.This location result supports the analysis of the alternating algorithm.
Algorithmic guarantees: Any accumulation point of AA-P-BPDN has the limiting BPDN property, while an optimal P-BPDN solution is a stationary point of AA-P-BPDN.Thus, with a suitable termination criterion, the algorithm's output can be treated as arbitrarily close to a stationary point.
Limitations: The convex relaxation for the positive-and-negative decomposition does not apply to the complex signal case, and it remains open whether its optimal solutions always satisfy the complementarity constraint.These are explicit scope and theory limitations of that relaxation.

C. Effectiveness of AA-P-BPDN

The paper evaluates AA-P-BPDN by checking whether its output satisfies the sufficient effectiveness condition for good recovery. Across more than 3700 trials, the required ℓ1-norm inequality held in every experiment.

Effectiveness criterion: AA-P-BPDN is assessed by checking whether its feasible output xAA satisfies ∥xAA∥1 ≤∥xo∥1.This is the effectiveness condition identified by Corollary 1 for a good recovery.
Numerical verification: Over 3700 trials, the inequality ∥xAA∥1 ≤∥xo∥1 held in all experiments.The simulations therefore verified the stated effectiveness criterion across the reported trials.

V. NUMERICAL SIMULATIONS

Numerical experiments test recovery under varying noise, perturbation, and measurement counts, then evaluate the method on positive sparse signals and DOA estimation. The results generally support robust recovery, with performance near ideal recovery under moderate perturbations.

A. Verification of the Robust Stability: AA-P-BPDN recovery errors for both the signal and βo are proportional to the noise level, while achieving the smallest non-oracle error.The comparison includes O-BPDN, N-BPDN, and TPS-BPDN.
A. Verification of the Robust Stability: AA-P-BPDN error slowly increases with perturbation level and remains close to ideal O-BPDN for moderate perturbations.O-BPDN maintains nearly constant error because it assumes the perturbation is known.
A. Verification of the Robust Stability: For signal recovery error 0.05, O-BPDN requires about 55 measurements, AA-P-BPDN 65, and TPS-BPDN 95.All approaches improve as the number of measurements increases, while N-BPDN does not reach this error in the reported observation.
A. Verification of the Robust Stability: A positive sparse signal with k = 10 unit spikes is exactly recovered from m = 50 noise-free measurements using PP-BPDN with r = 0.1.The recovery solves (P1).
B. Empirical Results of DOA Estimation: In DOA estimation, P-BPDN produces concentrated estimation errors, while SP-CS yields a single peak near the true source and standard CS produces displaced multiple peaks.The comparison uses a standard-CS grid with n = 360, whereas SP-CS jointly estimates off-grid distance on a coarser grid.
VI. CONCLUSION: The paper concludes that recovery error is proportional to measurement noise and exact in the special noise-free case, while DOA simulations provide satisfactory estimation results.The simulations also indicate that the RIP condition used for robust stability is conservative in practice, and joint sparsity is not exploited.

APPENDIX A PROOF OF THEOREM 3

The appendix proves exact recovery for the noiseless perturbed-CS formulation by recasting the problem with an augmented sparse representation and applying D-RIP-based arguments. The proof establishes uniqueness through sparsity and null-space control.

APPENDIX A PROOF OF THEOREM 3: The true and recovered augmented vectors are 2k-D-sparse, so their difference is 4k-D-sparse.This sparsity structure enables the D-RIP uniqueness step.
APPENDIX A PROOF OF THEOREM 3: When ¯δ4k < 1, the D-RIP forces the difference between the true and recovered augmented vectors to vanish in the noiseless case.The proof uses Ψ(zo − z∗) = 0 together with the 4k-D-sparsity of zo − z∗.
APPENDIX A PROOF OF THEOREM 3: P-BPDN is rewritten in augmented variables z, zo, and z∗ to incorporate the structured perturbation into the recovery analysis.The reformulation connects the perturbed sensing model to a D-RIP argument.
APPENDIX A PROOF OF THEOREM 3: The noisy proof decomposes the recovery error h into k-sparse blocks and bounds its leading block before controlling the remaining blocks.The argument follows the standard compressed-sensing error-decomposition pattern.
APPENDIX A PROOF OF THEOREM 3: The measurement residual is bounded by 2ϵ, and D-RIP inequalities are then used to control the error norm.The proof combines residual control, block estimates, and D-RIP bounds.
APPENDIX A PROOF OF THEOREM 3: The derived conditions are meaningful when c0 < 1, which completes the theorem’s sufficient-condition argument.The proof also relates δk(B) and δ2k(B) to ¯δ4k in the intermediate bounds.

APPENDIX C PROOF OF LEMMA 1

The lemma is proved by handling interior and boundary points separately. Interior feasibility is obtained through convergent approximating sequences, while boundary points are approached by interior points.

APPENDIX C PROOF OF LEMMA 1: For an interior point v, the proof constructs a sequence v(j) converging to v while preserving feasibility for sufficiently large j.The construction uses Φ(j) → Φ∗ and the slack η = ϵ − ϵ0.
APPENDIX C PROOF OF LEMMA 1: For a boundary point v, the proof selects interior points v(l) converging to v and applies the interior-point argument to each.This extends the result from interior points to the boundary of D∗.

APPENDIX D PROOF OF THEOREM 7

The proof establishes convergence and optimality properties for the alternating perturbed-CS procedure by extracting accumulation points and passing feasibility and objective inequalities to the limit.

APPENDIX D PROOF OF THEOREM 7: The proof first establishes existence of an accumulation point for the sequence generated by the algorithm.Boundedness follows from feasible iterates and bounded β(j) variables.
APPENDIX D PROOF OF THEOREM 7: Passing to the limit in the alternating minimization inequalities shows that an accumulation point satisfies the corresponding limiting optimization inequalities.The argument holds for all β in the bounded interval [−r, r]n.
APPENDIX D PROOF OF THEOREM 7: The objective sequence is decreasing, and the accumulation point is shown to satisfy the limiting conclusion for every x in D∗.The proof concludes the stated limiting relation after taking the sequence limit.
APPENDIX D PROOF OF THEOREM 7: Continuity of A + B∆(jl) and the feasibility lemma provide convergent feasible sequences approaching any point in the limiting feasible set.This connects finite-iteration feasible sets with the limiting set D∗.

APPENDIX E PROOF OF THEOREM 8

The proof establishes the optimality conditions by separating the cases ||y||_2 ≤ ϵ and ||y||_2 > ϵ. In the latter case, contradiction follows by constructing a feasible solution with strictly smaller ℓ1 norm.

When ||y||_2 ≤ ϵ, the optimal solution is x* = 0, so condition (23) holds for any β* ∈ [−r, r]^n.
When ||y||_2 > ϵ, the residual satisfies ||y − (A + B∆*)x*||_2 = ϵ by condition (22) and Lemma 2.
Assuming condition (23) fails yields a feasible but nonoptimal solution for the auxiliary problem.
An optimal solution x′ to problem (40) has ||x′||_1 < ||x*||_1, while the associated construction is feasible for P-BPDN problem (11).
The strict norm improvement contradicts optimality of (x*, β*) for P-BPDN problem (11), proving condition (23).