Cosparsity in compressed sensing. (English) Zbl 1333.94020
Boche, Holger (ed.) et al., Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013. Cham: Birkhäuser/Springer (ISBN 978-3-319-16041-2/hbk; 978-3-319-16042-9/ebook). Applied and Numerical Harmonic Analysis, 315-339 (2015).
Summary: Analysis \(\ell_1\)-recovery is a strategy of acquiring a signal, that is sparse in some transform domain, from incomplete observations. In this chapter we give an overview of the analysis sparsity model and present theoretical conditions that guarantee successful nonuniform and uniform recovery of signals from noisy measurements. We derive a bound on the number of Gaussian and subgaussian measurements by examining the provided theoretical guarantees under the additional assumption that the transform domain is generated by a frame, which means that there are just few nonzero inner products of a signal of interest with frame elements.
For the entire collection see [Zbl 1320.94007].
For the entire collection see [Zbl 1320.94007].
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
References:
| [1] | Benedetto, J. J.; Heil, C.; Walnut, D. F., Differentiation and the Balian-Low theorem, J. Fourier Anal. Appl., 1, 4, 355-402 (1994) · Zbl 0887.42026 · doi:10.1007/s00041-001-4016-5 |
| [2] | Blumensath, T., Sampling and reconstructing signals from a union of linear subspaces, IEEE Trans. Inf. Theory, 57, 7, 4660-4671 (2011) · Zbl 1365.94173 · doi:10.1109/TIT.2011.2146550 |
| [3] | Blumensath, T.; Davies, M. E., Sampling theorems for signals from the union of finite-dimensional linear subspaces, IEEE Trans. Inf. Theory, 55, 4, 1872-1882 (2009) · Zbl 1367.94144 · doi:10.1109/TIT.2009.2013003 |
| [4] | Burger, M.; Osher, S., Convergence rates of convex variational regularization, Inverse Prob., 20, 5, 1411-1421 (2004) · Zbl 1068.65085 · doi:10.1088/0266-5611/20/5/005 |
| [5] | Cai, J.-F., Xu, W.: Guarantees of total variation minimization for signal recovery. In: Proceedings of 51st Annual Allerton Conference on Communication, Control, and Computing, 1266-1271 (2013) |
| [6] | Candès, E. J.; Donoho, D. L., New tight frames of curvelets and optimal representations of objects with piecewise C^2 singularities, Commun. Pure Appl. Math., 57, 2, 219-266 (2004) · Zbl 1038.94502 · doi:10.1002/cpa.10116 |
| [7] | Candès, E. J.; Eldar, Y. C.; Needell, D.; Randall, P., Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31, 1, 59-73 (2011) · Zbl 1215.94026 · doi:10.1016/j.acha.2010.10.002 |
| [8] | Candès, E. J.; Tao, J. T.; Romberg, J. K., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [9] | Carrillo, R.E., McEwen, J.D., Van De Ville, D., Thiran, J.-Ph., Wiaux, Yv.: Sparsity averaging for compressive imaging. IEEE Signal Process Lett. 20(6), 591-594 (2013) |
| [10] | Casazza, P. G.; Kutyniok, G., Finite frames (2013), New York: Theory and applications. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York · Zbl 1257.42001 |
| [11] | Chan, T.; Shen, J., Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods (2005), Philadelphia: SIAM, Philadelphia · Zbl 1095.68127 · doi:10.1137/1.9780898717877 |
| [12] | Chandrasekaran, V.; Recht, B.; Parrilo, P. A.; Willsky, A. S., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 6, 805-849 (2012) · Zbl 1280.52008 · doi:10.1007/s10208-012-9135-7 |
| [13] | Chen, Y., Pock, Th., Bischof, H.: Learning ℓ_1-based analysis and synthesis sparsity priors using bi-level optimization. Preprint arXiv:1401.4105 (2014) |
| [14] | Christensen, O., An Introduction to Frames and Riesz Bases (2003), Birkhäuser, Boston: Applied and Numerical Harmonic Analysis, Birkhäuser, Boston · Zbl 1017.42022 · doi:10.1007/978-0-8176-8224-8 |
| [15] | Davenport, M.; Wakin, M., Analysis of orthogonal matching pursuit using the restricted isometry property, IEEE Trans. Inf. Theory, 56, 9, 4395-4401 (2010) · Zbl 1366.94093 · doi:10.1109/TIT.2010.2054653 |
| [16] | Duffin, R. J.; Schaeffer, A. C., A class of nonharmonic Fourier series, Trans. Am. Math. Soc., 72, 2, 341-366 (1952) · Zbl 0049.32401 · doi:10.1090/S0002-9947-1952-0047179-6 |
| [17] | Elad, M.; Milanfar, P.; Rubinstein, R., Analysis versus synthesis in signal priors, Inverse Prob., 23, 3, 947-968 (2007) · Zbl 1138.93055 · doi:10.1088/0266-5611/23/3/007 |
| [18] | Fadili, J., Peyré, G., Vaiter, S., Deledalle, C.-A., Salmon, J.: Stable recovery with analysis decomposable priors. In: 10th international conference on Sampling Theory and Applications (SampTA 2013), pp. 113-116, Bremen, Germany (2013) |
| [19] | Foucart, S., Stability and robustness of ℓ_1-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl., 441, 4-21 (2014) · Zbl 1332.94042 · doi:10.1016/j.laa.2012.10.003 |
| [20] | Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), Birkhäuser, Boston: Applied and Numerical Harmonic Analysis, Birkhäuser, Boston · Zbl 1315.94002 · doi:10.1007/978-0-8176-4948-7 |
| [21] | Fuchs, J. J., On sparse representations in arbitrary redundant bases, IEEE Trans. Inf. Theory, 50, 6, 1341-1344 (2004) · Zbl 1284.94018 · doi:10.1109/TIT.2004.828141 |
| [22] | Giryes, R.; Nam, S.; Elad, M.; Gribonval, R.; Davies, M. E., 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 |
| [23] | Gordon, Y.: On Milman’s inequality and random subspaces which escape through a mesh in \(\mathbb{R}^n \) . In: Geometric Aspects of Functional Analysis (1986/87) 1317 of Lecture Notes in Mathematics, pp. 84-106, Springer, Berlin (1988) · Zbl 0651.46021 |
| [24] | Grasmair, M., Linear convergence rates for Tikhonov regularization with positively homogeneous functionals, Inverse Prob., 27, 7, 075014 (2011) · Zbl 1219.35359 · doi:10.1088/0266-5611/27/7/075014 |
| [25] | Gröchenig, K., Foundations of time-frequency analysis (2001), Birkhäuser, Boston: Appl. Numer. Harmon. Anal, Birkhäuser, Boston · Zbl 0966.42020 · doi:10.1007/978-1-4612-0003-1 |
| [26] | Guo, K., Kutyniok, G., Labate, D.: Sparse multidimensional representations using anisotropic dilation and shear operators In: Chen, G., Lai, M. (eds.), Wavelets and Splines: Athens 2005, Proceedings of the International Conference on the Interactions Between Wavelets and Splines, Athens, GA, May 16-19 (2005) · Zbl 1099.65148 |
| [27] | Haltmeier, M., Stable signal reconstruction via ℓ^1-minimization in redundant, non-tight frames, IEEE Trans. Signal Process., 61, 2, 420-426 (2013) · Zbl 1393.94254 · doi:10.1109/TSP.2012.2222396 |
| [28] | Hawe, S., Kleinsteuber, M., Diepold,Kl.: Analysis operator learning and its application to image reconstruction. IEEE Trans. Image Process. 22(6), 2138-2150 (2013) · Zbl 1373.94161 |
| [29] | Kabanava, M., Rauhut, H.: Analysis ℓ_1-recovery with frames and Gaussian measurements. Preprint arXiv:1306.1356 (2013) · Zbl 1378.94008 |
| [30] | Kabanava, M., Rauhut, H., Zhang, H.: Robust analysis ℓ_1-recovery from Gaussian measurements and total variation minimization. Preprint arXiv:1407.7402 (2014) · Zbl 1387.94039 |
| [31] | Krahmer, F.; Mendelson, S.; Rauhut, H., Suprema of chaos processes and the restricted isometry property, Commun. Pure Appl. Math., 67, 11, 1877-1904 (2014) · Zbl 1310.94024 · doi:10.1002/cpa.21504 |
| [32] | Krahmer, F.; Ward, R., Stable and robust sampling strategies for compressive imaging, IEEE Trans. Image Process., 23, 2, 612-622 (2014) · Zbl 1374.94181 · doi:10.1109/TIP.2013.2288004 |
| [33] | Ledoux, M.; Talagrand, M., Probability in Banach Spaces (1991), Berlin, Heidelberg, NewYork: Springer, Berlin, Heidelberg, NewYork · Zbl 0748.60004 · doi:10.1007/978-3-642-20212-4 |
| [34] | Liu, Y.; Mi, T.; Li, Sh., Compressed sensing with general frames via optimal-dual-based ℓ_1-analysis, IEEE Trans. Inf. Theory, 58, 7, 4201-4214 (2012) · Zbl 1365.94181 · doi:10.1109/TIT.2012.2191612 |
| [35] | Mallat, S., A Wavelet Tour of Signal Processing: The Sparse Way (2008), San Diego: Academic, San Diego |
| [36] | Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N., Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. Funct. Anal., 17, 4, 1248-1282 (2007) · Zbl 1163.46008 · doi:10.1007/s00039-007-0618-7 |
| [37] | Nam, S., Davies, M.E., Elad, M., Gribonval, R.: Cosparse analysis modeling – uniqueness and algorithms. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2011) · Zbl 1261.94018 |
| [38] | Nam, S.; Davies, M. E.; Elad, M.; Gribonval, R., The cosparse analysis model and algorithms, Appl. Comput. Harmon. Anal., 34, 1, 30-56 (2013) · Zbl 1261.94018 · doi:10.1016/j.acha.2012.03.006 |
| [39] | Needell, D.; Ward, R., Stable image reconstruction using total variation minimization, SIAM J. Imag. Sci., 6, 2, 1035-1058 (2013) · Zbl 1370.94042 · doi:10.1137/120868281 |
| [40] | Peleg, T.; Elad, M., Performance guarantees of the thresholding algorithm for the cosparse analysis model, IEEE Trans. Inf. Theory., 59, 3, 1832-1845 (2013) · Zbl 1364.94152 · doi:10.1109/TIT.2012.2226924 |
| [41] | Rauhut, H., Random sampling of sparse trigonometric polynomials, Appl. Comput. Harmon. Anal., 22, 1, 16-42 (2007) · Zbl 1123.94004 · doi:10.1016/j.acha.2006.05.002 |
| [42] | Rauhut, H.: Circulant and Toeplitz matrices in compressed sensing. In: Proceedings on SPARS’09, Saint-Malo, France (2009) |
| [43] | Rauhut, H.: Compressive sensing and structured random matrices. In: Fornasier M. (ed.) Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Series on Computational and Applied Mathematics, vol. 9, pp. 1-92. deGruyter (2010) · Zbl 1208.15027 |
| [44] | Rauhut, H.; Romberg, J. K.; Tropp, J. A., Restricted isometries for partial random circulant matrices, Appl. Comput. Harmon. Anal., 32, 2, 242-254 (2012) · Zbl 1245.15040 · doi:10.1016/j.acha.2011.05.001 |
| [45] | Romberg, J. K., Compressive sensing by random convolution, SIAM J. Imag. Sci., 2, 4, 1098-1128 (2009) · Zbl 1176.94017 · doi:10.1137/08072975X |
| [46] | Ron, A.; Shen, Z., Affine systems in L_2(R^d): the analysis of the analysis operator, J. Funct. Anal., 148, 2, 408-447 (1997) · Zbl 0891.42018 · doi:10.1006/jfan.1996.3079 |
| [47] | Rubinstein, R.; Peleg, T.; Elad, M., Analysis K-SVD: a dictionary-learning algorithm for the analysis sparse model, IEEE Trans. Signal Process., 61, 3, 661-677 (2013) · Zbl 1393.94416 · doi:10.1109/TSP.2012.2226445 |
| [48] | Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., 61, 8, 1025-1045 (2008) · Zbl 1149.94010 · doi:10.1002/cpa.20227 |
| [49] | Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [50] | Selesnick, I.; Figueiredo, M., Signal restoration with overcomplete wavelet transforms: comparison of analysis and synthesis priors, Proc. SPIE, 7446, 74460D (2009) · doi:10.1117/12.826663 |
| [51] | Tropp, J. A., Recovery of short, complex linear combinations via l_1 minimization, IEEE Trans. Inf. Theory, 51, 4, 1568-1570 (2005) · Zbl 1288.94020 · doi:10.1109/TIT.2005.844057 |
| [52] | Vaiter, S., Golbabaee, M., Fadili, J.M., Peyré, G.: Model selection with low complexity priors. Preprint arXiv:1307.2342 (2013) · Zbl 1386.94040 |
| [53] | Vaiter, S.; Peyré, G.; Dossal, Ch.; Fadili, J., Robust sparse analysis regularization, IEEE Trans. Inf. Theory, 59, 4, 2001-2016 (2013) · Zbl 1364.94172 · doi:10.1109/TIT.2012.2233859 |
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.
