Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T07:10:01.410Z Has data issue: false hasContentIssue false
  • English
  • Français

Robust analysis ℓ1-recovery from Gaussian measurements and total variation minimization†

Published online by Cambridge University Press:  01 June 2015

M. KABANAVA ,
H. RAUHUT  and
H. ZHANG
M. KABANAVA
Affiliation:
Chair for Mathematics C (Analysis), RWTH Aachen University, Templegraben 55, 52062 Aachen, Germany email: [email protected]; [email protected]
H. RAUHUT
Affiliation:
Chair for Mathematics C (Analysis), RWTH Aachen University, Templegraben 55, 52062 Aachen, Germany email: [email protected]; [email protected]
H. ZHANG
Affiliation:
College of Science, National University of Defense Technology, Changsha, Hunan, 410073China email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Analysis ℓ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.

Keywords

compressive sensingℓ1-minimizationTV-normframesGaussian random matrices
Type
Papers
Information
European Journal of Applied Mathematics , Volume 26 , Issue 6 , December 2015 , pp. 917 - 929
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

M. Kabanava and H. Rauhut acknowledge support by the European Research Council through the grant StG 258926. H. Zhang is supported by China NSF Grants No. 61201328.

References

[1]Amelunxen, D., Lotz, M., McCoy, M. B. & Tropp, J. A. (2014) Living on the edge: Phase transitions in convex programs with random data. Inform. Inference 3 (3), 224–294.CrossRefGoogle Scholar
[2]Cai, J. & Xu, W. (2013) Guarantees of total variation minimization for signal recovery. In: Conference on Communication, Control, and Computing (Allerton). University of Illinois at Urbana-Champaign, Monticello, IL, USA.Google Scholar
[3]Candès, E. J., Eldar, Y. C., Needell, D. & Randall, P. (2011) Compressed sensing with coherent and redundant dictionaries. Appl. Comput. Harmon. Anal. 31 (1), 59–73.CrossRefGoogle Scholar
[4]Chandrasekaran, V., Recht, B., Parrilo, P. & Willsky, A. (2012) The convex geometry of linear inverse problems. Found. Comput. Math. 12 (6), 805–849.CrossRefGoogle Scholar
[5]Elad, M., Milanfar, P. & Rubinstein, R. (2007) Analysis versus synthesis in signal priors. Inverse Problems 23 (3), 947–968.CrossRefGoogle Scholar
[6]Eldar, Y. & Kutyniok, G. (editors) (2012) Compressed Sensing - Theory and Applications, Cambridge University Press, New York.CrossRefGoogle Scholar
[7]Foucart, S. & Rauhut, H. (2013) A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis, Springer, New York.CrossRefGoogle Scholar
[8]Foygel, R. & Mackey, L. (Feb. 2014) Corrupted sensing: Novel guarantees for separating structured signals. IEEE Trans. Inform. Theory 60 (2), 1223–1247.CrossRefGoogle Scholar
[9]Giryes, R., Nam, S., Elad, M., Gribonval, R. & Davies, M. (2014) Greedy-like algorithms for the cosparse analysis model. Linear Algebra Appl. 441 (0), 22–60.CrossRefGoogle Scholar
[10]Gordon, Y. (1988) On Milman's inequality and random subspaces which escape through a mesh in ${\mathbb R}^n$. In: Geometric Aspects of Functional Analysis (1986/87), Lecture Notes in Math., Vol. 1317, Springer Berlin Heidelberg, pp. 84–106.CrossRefGoogle Scholar
[11]Kabanava, M. & Rauhut, H. (2014) Analysis ℓ1-recovery with frames and Gaussian measurements. Acta Appl. Math., doi:10.1007/s10440-014-9984-y.Google Scholar
[12]Kabanava, M. & Rauhut, H. Cosparsity in compressed sensing. In: Compressed Sensing and Its Applications, Springer, to appear.Google Scholar
[13]Nam, S., Davies, M., Elad, M. & Gribonval, R. (2013) The cosparse analysis model and algorithms. Appl. Comput. Harmon. Anal. 34 (1), 30–56.CrossRefGoogle Scholar
[14]Needell, D. & Ward, R. (2013) Near-optimal compressed sensing guarantees for total variation minimization. IEEE Trans. Image Process. 22 (10), 3941–3949.CrossRefGoogle ScholarPubMed
[15]Needell, D. & Ward, R. (2013) Stable image reconstruction using total variation minimization. SIAM J. Imag. Sci. 6 (2), 1035–1058.CrossRefGoogle Scholar
[16]Stojnic, M. (2009) Various thresholds for ℓ1-optimization in compressed sensing. ArXiv e-prints.Google Scholar
[17]Tropp, J. A. Convex recovery of a structured signal from independent random linear measurements. Sampling Theory, a Renaissance, to appear.Google Scholar