Signal recovery under mutual incoherence property and oracle inequalities

Abstract

We consider the signal recovery through an unconstrained minimiza-tion in the framework of mutual incoherence property. A sufficient condition is provided to guarantee the stable recovery in the noisy case. Furthermore, oracle inequalities of both sparse signals and non-sparse signals are derived under the mutual incoherence condition in the case of Gaussian noises. Finally, we investigate the relationship between mutual incoherence property and robust null space property and find that robust null space property can be deduced from the mutual incoherence property.

Keywords

Mutual incoherence property (MIP) / Lasso / Dantzig selector / oracle inequality / robust null space property (RNSP)

References

[1] Bickel P J, Ritov Y, Tsybakov A B. Simultaneous analysis of Lasso and Dantzig selector. Ann Statist, 2009, 37: 1705–1732

[2] Cai T T, Wang L, Xu G. Stable recovery of sparse signals and an oracle inequality. IEEE Trans Inform Theory, 2010, 56: 3516–3522

[3] Cai T T, Xu G, Zhang J. On recovery of sparse signals via l₁ minimization. IEEE Trans Inform Theory, 2009, 55: 3388–3397

[4] Cai T T, Zhang A. Compressed sensing and affine rank minimization under restricted isometry. IEEE Trans Inform Theory, 2013, 61: 3279–3290

[5] Cai T T,Zhang A. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans Inform Theory, 2014, 60: 122–132

[6] Candès E J, Plan Y. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans Inform Theory, 2011, 57: 2342–2359

[7] Candès E J, Romberg J K, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Comm Pure Appl Math, 2006, 59: 1207–1223

[8] Candès E J, Tao T. Decoding by linear programming. IEEE Trans Inform Theory, 2005, 51: 4203–4215

[9] Candès E J, Tao T. Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans Inform Theory, 2006, 52: 5406–5425

[10] Candès E J, Tao T. The Dantzig selector: Statistical estimation when p is much larger than n: Ann Statist, 2007, 33: 2313–2351

[11] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM J Sci Comput, 1998, 20: 33–61

[12] Cohen A, Dahmen W, DeVore R. Compressed sensing and best k-term approximation. J Amer Math Soc, 2009, 22: 211–231

[13] De Castro Y. A remark on the Lasso and the Dantzig selector. Statist Probab Lett, 2013, 83: 304–314

[14] Donoho D L. Compressed sensing. IEEE Trans Inform Theory, 2006, 52: 1289–1306

[15] Donoho D L, Elad M. Optimally sparse representations in general (nonorthogonal) dictionaries via l₁ minimization. Proc Natl Acad Sci USA, 2003, 100: 2197–2202

[16] Donoho D L, Elad M, Temlyakov V N. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans Inform Theory, 2005, 52: 6–18

[17] Donoho D L, Huo X. Uncertainty principles and ideal atomic decomposition. IEEE Trans Inform Theory, 2001, 47: 2845–2862

[18] Donoho D L, Johnstone I M. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 1994, 81: 425–455

[19] Elad M, Milanfar P, Rubinstein R. Analysis versus synthesis in signal priors. Inverse Problems, 2007, 23: 947–968

[20] Erickson S, Sabatti C. Empirical Bayes estimation of a sparse vector of gene expression changes. Stat Appl Genet Mol Biol, 2005, 4: 1–27

[21] Foucart S. Stability and robustness of l₁-minimizations with Weibull matrices and redundant dictionaries. Linear Algebra Appl, 2014, 441: 4–21

[22] Fourcat S. Flavors of compressive sensing. In: Fasshauer G E, Schumaker L L, eds. International Conference Approximation Theory, Approximation Theory XV, San Antonio. 2016, 61–104

[23] Foucart S, Rauhut H. A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis Series. New York: Birkhauser, 2013

[24] Herman M, Strohmer T. High-resolution radar via compressed sensing. IEEE Trans. Signal Process., 2009, 57: 2275–2284

[25] Li P, Chen W G. Signal recovery under cumulative coherence. J Comput Appl Math, 2019, 346: 399–417

[26] Lin J H, Li S. Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO. Appl Comput Harmon Anal, 2014, 37: 126–139

[27] Lustig M. Donoho D L, Pauly J M. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007, 58: 1182–1195

[28] Parvaresh F, Vikalo H, Misra S, Hassibi B. Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays. IEEE J Sel Top Signal Process, 2008, 2: 275–285

[29] Schnass K, Vandergheynst P. Dictionary preconditioning for greedy algorithms. IEEE Trans Signal Process, 2008, 56: 1994–2002

[30] Shen Y, Han B, Braverman E. Stable recovery of analysis based approaches. Appl Comput Harmon Anal, 2015, 39: 161–172

[31] Sun Q. Sparse approximation property and stable recovery of sparse signals from noisy measurements. IEEE Trans Signal Process, 2011, 59: 5086–5090

[32] Tan Z, Eldar Y C, Beck A, Nehorai A. Smoothing and decomposition for analysis sparse recovery. IEEE Trans Signal Process, 2014, 62: 1762–1774

[33] Tauböck G, Hlawatsch F, Eiwen D, Rauhut H. Compressive estimation of doubly selective channels in multicarrier systems: leakage effects and sparsity-enhancing processing. IEEE J Sel Top Signal Process, 2010, 4: 255–271

[34] Tibshirani R. Regression shrinkage and selection via the Lasso. J R Stat Soc Ser B, 1996, 58: 267–288

[35] Tropp J A. Greed is good: algorithmic results for sparse approximation. IEEE Trans Inform Theory, 2004, 50: 2231–2242

[36] Tseng P. Further results on a stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans Inform Theory, 2009, 55: 888–899

[37] Vasanawala S, Alley M, Hargreaves B, Barth R, Pauly J, Lustig M. Improved pediatric MR imaging with compressed sensing. Radiology, 2010, 256: 607–616

[38] Wojtaszczyk P. Stability and instance optimality for Gaussian measurements in compressed sensing. Found Comput Math, 2010, 10: 1–13

[39] Xia Y, Li S. Analysis recovery with coherent frames and correlated measurements. IEEE Trans Inform Theory, 2016, 62: 6493–6507

[40] Zhang H, Yan M, Yin W. One condition for solution uniqueness and robustness of both l₁-synthesis and l1-analysis minimizations. Adv Comput Math, 2016, 42: 1381–1399

[41] Zhang R, Li S. A proof of conjecture on restricted isometry property constants δ_tk (0<t<4=3): IEEE Trans Inform Theory, 2018, 65: 1699–1705

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature