×

Robust analysis \(\ell_1\)-recovery from Gaussian measurements and total variation minimization. (English) Zbl 1387.94039

Summary: Analysis \(\ell_1\)-recovery refers to a technique of recovering a signal that is sparse in some transform domain from incomplete corrupted measurements. This includes total variation minimization as an important special case when the transform domain is generated by a difference operator. In the present paper, we provide a bound on the number of Gaussian measurements required for successful recovery for total variation and for the case that the analysis operator is a frame. The bounds are particularly suitable when the sparsity of the analysis representation of the signal is not very small.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A20 Sampling theory in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amelunxen, D.; Lotz, M.; Mccoy, M. B.; Tropp, J. A., Living on the edge: Phase transitions in convex programs with random data., Inform. Inference, 3, 224-294, (2014) · Zbl 1339.90251 · doi:10.1093/imaiai/iau005
[2] Cai, J.; Xu, W., (2013)
[3] Candès, E. J.; Eldar, Y. C.; Needell, D.; Randall, P., Compressed sensing with coherent and redundant dictionaries., Appl. Comput. Harmon. Anal., 31, 59-73, (2011) · Zbl 1215.94026 · doi:10.1016/j.acha.2010.10.002
[4] Chandrasekaran, V.; Recht, B.; Parrilo, P.; Willsky, A., The convex geometry of linear inverse problems., Found. Comput. Math., 12, 805-849, (2012) · Zbl 1280.52008 · doi:10.1007/s10208-012-9135-7
[5] Elad, M.; Milanfar, P.; Rubinstein, R., Analysis versus synthesis in signal priors., Inverse Problems, 23, 947-968, (2007) · Zbl 1138.93055 · doi:10.1088/0266-5611/23/3/007
[6] Eldar, Y.; Kutyniok, G., Compressed Sensing - Theory and Applications, (2012), Cambridge University Press: Cambridge University Press, New York
[7] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, (2013), Applied and Numerical Harmonic Analysis, Springer: Applied and Numerical Harmonic Analysis, Springer, New York · Zbl 1315.94002
[8] Foygel, R.; Mackey, L., Corrupted sensing: Novel guarantees for separating structured signals, IEEE Trans. Inform. Theory, 60, 1223-1247, (2014) · Zbl 1364.94124 · doi:10.1109/TIT.2013.2293654
[9] Giryes, R.; Nam, S.; Elad, M.; Gribonval, R.; Davies, M., Greedy-like algorithms for the cosparse analysis model., Linear Algebra Appl., 441, 22-60, (2014) · Zbl 1332.94043 · doi:10.1016/j.laa.2013.03.004
[10] Gordon, Y., On Milman’s inequality and random subspaces which escape through a mesh in \({\mathbb R}^n\), Geometric Aspects of Functional Analysis (1986/87), 84-106, (1988), Springer: Springer, Berlin Heidelberg
[11] Kabanava, M.; Rauhut, H., Analysis ℓ_1-recovery with frames and Gaussian measurements, Acta Appl. Math., (2014) · Zbl 1378.94008 · doi:10.1007/s10440-014-9984-y
[12] Kabanava, M.; Rauhut, H.
[13] Nam, S.; Davies, M.; Elad, M.; Gribonval, R., The cosparse analysis model and algorithms., Appl. Comput. Harmon. Anal., 34, 30-56, (2013) · Zbl 1261.94018 · doi:10.1016/j.acha.2012.03.006
[14] Needell, D.; Ward, R., Near-optimal compressed sensing guarantees for total variation minimization., IEEE Trans. Image Process., 22, 3941-3949, (2013) · Zbl 1373.94673 · doi:10.1109/TIP.2013.2264681
[15] Needell, D.; Ward, R., Stable image reconstruction using total variation minimization., SIAM J. Imag. Sci., 6, 1035-1058, (2013) · Zbl 1370.94042 · doi:10.1137/120868281
[16] Stojnic, M., (2009)
[17] Tropp, J. A.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.