Robustly Stable Signal Recovery in Compressed Sensing With Structured Matrix Perturbation

Zai Yang, Cishen Zhang, Lihua XieIEEE TSP 2011 · DOI · OpenReview

Abstract

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.

Introduction

In the classic Compressed Sensing (CS) model, we recover a sparse signal $x$ from measurements $y = \Phi x + e$. Crucially, standard theory assumes the sensing matrix $\Phi$ is known exactly. In practice, this is rarely true; instruments have calibration errors, and "off-grid" effects in radar or sonar mean the true signal doesn't align perfectly with a discretized model.

Previous research showed that if $\Phi$ is perturbed by an unknown matrix $E$, the recovery error is at best proportional to the size of that perturbation. This paper introduces a framework for robustly stable recovery—where the recovery error vanishes as measurement noise goes to zero—by modeling these perturbations as having known directions but unknown magnitudes.

Methodology

Structured Matrix Perturbation

The authors focus on a model where the sensing matrix is $\Phi = A + B\Delta^o$. Here, $A$ is the known nominal matrix, $B$ is a known matrix defining the direction of the perturbation, and $\Delta^o$ is an unknown diagonal matrix representing the magnitude of the perturbation at each entry.

Theoretical Framework

To provide guarantees, the authors extend the standard Restricted Isometry Property (RIP) to a new version called Duplicate RIP (D-RIP). This metric evaluates how well the combined matrix $[A, B]$ preserves the energy of "duplicately sparse" vectors. They formulate the Perturbed Basis Pursuit Denoising (P-BPDN) optimization problem, which seeks to minimize the $\ell_1$ norm of the signal while constrained by a total error term that includes the structured perturbation.

Geometric interpretation of the recovery error under structured perturbation.

As shown in Figure 1, the recovery process can be interpreted geometrically. The diamond represents the $\ell_1$ ball, while the hatched region represents the feasible set defined by the perturbed measurements. The recovery error is bounded by the distance between the true signal $x^o$ and the recovered signal $x^*$, which is the point in the feasible set with the minimum $\ell_1$ norm.

Algorithms

  • For Positive Signals: The problem can be transformed into a purely convex one, allowing for global optimality.
  • For General Signals: The authors propose AA-P-BPDN (Alternating Algorithm for P-BPDN), which iteratively swaps between estimating the signal $x$ and the perturbation magnitudes.

Key Results

Numerical simulations verify the theoretical bounds using synthetic sparse signals and Direction of Arrival (DOA) estimation models.

  • Stability: The authors prove that if the D-RIP constant is sufficiently small, the recovery error is bounded by a constant times the noise level $\epsilon$. In noise-free cases, exact recovery is possible.
  • Performance: The AA-P-BPDN algorithm significantly outperformed standard BPDN. For instance, in scenarios where standard BPDN failed due to perturbations, the proposed method achieved low recovery error with a reasonable number of measurements.
  • DOA Accuracy: In off-grid scenarios, the proposed method produced sharp peaks at correct locations, whereas standard CS produced multiple false peaks due to spectral leakage.

Conclusion and Future Work

By assuming the error occurs in a specific way (the $B$ matrix), the perturbation effectively becomes part of the signal to be recovered. This allows for grid independence in applications like DOA estimation. While the general P-BPDN problem is non-convex, the alternating algorithm works well in practice. Future work may involve exploiting joint sparsity techniques, such as Group Lasso, to further improve performance and relax the currently conservative RIP-based theoretical bounds.

Summary updated

Abstract

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 l 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 l 1 minimization problem and numerical simulations are carried out to verify the results obtained.
BibTeX
@article{yang2011robustly,
  author = {Zai Yang and Cishen Zhang and Lihua Xie},
  title = {{Robustly Stable Signal Recovery in Compressed Sensing With Structured Matrix Perturbation}},
  journal = {IEEE Trans. Signal Process.},
  year = {2011},
  doi = {10.1109/tsp.2012.2201152},
}
Figure