arrow
Volume 43, Issue 2
Oracle Inequalities for Corrupted Compressed Sensing

Liping Yin & Peng Li

J. Comp. Math., 43 (2025), pp. 461-492.

Published online: 2024-11

Export citation
  • Abstract

In this paper, we establish the oracle inequalities of highly corrupted linear observations $b = Ax_0 + f_0 + e ∈ \mathbb{R}^m.$ Here the vector $x_0 ∈ \mathbb{R}^n$ with $n ≫ m$ is a (approximately) sparse signal and $f_0 ∈ \mathbb{R}^m$ is a sparse error vector with nonzero entries that can be possible infinitely large, $e ∼\mathcal{ N} (0, σ^2 I_m)$ represents the Gaussian random noise vector. We extend the oracle inequality $||\hat{x}-x_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}$ for Dantzig selector and Lasso models in [E.J. Candès and T. Tao, Ann. Statist., 35 (2007), 2313–2351] and [T.T. Cai, L. Wang, and G. Xu, IEEE Trans. Inf. Theory, 56 (2010), 3516–3522] to $||\hat{x}-x_0||^2_2+||\hat{f}-f_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}+\sum_j{\rm min}\{|\lambda f_0(j)|^2,\sigma^2\}$ for the extended Dantzig selector and Lasso models. Here $(\hat{x}, \hat{f})$ is the solution of the extended model, and $λ > 0$ is the balance parameter between $||x||_1$ and $||f||_1$ i.e. $||x||_1+\lambda||f||_1.$

  • AMS Subject Headings

Primary 94A12, 62G05, Secondary 90C25

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-43-461, author = {Yin , Liping and Li , Peng}, title = {Oracle Inequalities for Corrupted Compressed Sensing}, journal = {Journal of Computational Mathematics}, year = {2024}, volume = {43}, number = {2}, pages = {461--492}, abstract = {

In this paper, we establish the oracle inequalities of highly corrupted linear observations $b = Ax_0 + f_0 + e ∈ \mathbb{R}^m.$ Here the vector $x_0 ∈ \mathbb{R}^n$ with $n ≫ m$ is a (approximately) sparse signal and $f_0 ∈ \mathbb{R}^m$ is a sparse error vector with nonzero entries that can be possible infinitely large, $e ∼\mathcal{ N} (0, σ^2 I_m)$ represents the Gaussian random noise vector. We extend the oracle inequality $||\hat{x}-x_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}$ for Dantzig selector and Lasso models in [E.J. Candès and T. Tao, Ann. Statist., 35 (2007), 2313–2351] and [T.T. Cai, L. Wang, and G. Xu, IEEE Trans. Inf. Theory, 56 (2010), 3516–3522] to $||\hat{x}-x_0||^2_2+||\hat{f}-f_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}+\sum_j{\rm min}\{|\lambda f_0(j)|^2,\sigma^2\}$ for the extended Dantzig selector and Lasso models. Here $(\hat{x}, \hat{f})$ is the solution of the extended model, and $λ > 0$ is the balance parameter between $||x||_1$ and $||f||_1$ i.e. $||x||_1+\lambda||f||_1.$

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2310-m2022-0282}, url = {http://global-sci.org/intro/article_detail/jcm/23546.html} }
TY - JOUR T1 - Oracle Inequalities for Corrupted Compressed Sensing AU - Yin , Liping AU - Li , Peng JO - Journal of Computational Mathematics VL - 2 SP - 461 EP - 492 PY - 2024 DA - 2024/11 SN - 43 DO - http://doi.org/10.4208/jcm.2310-m2022-0282 UR - https://global-sci.org/intro/article_detail/jcm/23546.html KW - Corrupted compressed sensing, Oracle inequality, Extended Dantzig selector, Extended Lasso, Generalized restricted isometry property. AB -

In this paper, we establish the oracle inequalities of highly corrupted linear observations $b = Ax_0 + f_0 + e ∈ \mathbb{R}^m.$ Here the vector $x_0 ∈ \mathbb{R}^n$ with $n ≫ m$ is a (approximately) sparse signal and $f_0 ∈ \mathbb{R}^m$ is a sparse error vector with nonzero entries that can be possible infinitely large, $e ∼\mathcal{ N} (0, σ^2 I_m)$ represents the Gaussian random noise vector. We extend the oracle inequality $||\hat{x}-x_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}$ for Dantzig selector and Lasso models in [E.J. Candès and T. Tao, Ann. Statist., 35 (2007), 2313–2351] and [T.T. Cai, L. Wang, and G. Xu, IEEE Trans. Inf. Theory, 56 (2010), 3516–3522] to $||\hat{x}-x_0||^2_2+||\hat{f}-f_0||^2_2\lesssim \sum_i{\rm min}\{|x_0(i)|^2,\sigma^2\}+\sum_j{\rm min}\{|\lambda f_0(j)|^2,\sigma^2\}$ for the extended Dantzig selector and Lasso models. Here $(\hat{x}, \hat{f})$ is the solution of the extended model, and $λ > 0$ is the balance parameter between $||x||_1$ and $||f||_1$ i.e. $||x||_1+\lambda||f||_1.$

Yin , Liping and Li , Peng. (2024). Oracle Inequalities for Corrupted Compressed Sensing. Journal of Computational Mathematics. 43 (2). 461-492. doi:10.4208/jcm.2310-m2022-0282
Copy to clipboard
The citation has been copied to your clipboard