×

Uniform recovery of fusion frame structured sparse signals. (English) Zbl 1360.94061

Summary: We consider the problem of recovering fusion frame sparse signals from incomplete measurements. These signals are composed of a small number of nonzero blocks taken from a family of subspaces. First, we show that, by using a-priori knowledge of a coherence parameter associated with the angles between the subspaces, one can uniformly recover fusion frame sparse signals with a significantly reduced number of vector-valued (sub-)Gaussian measurements via mixed \(\ell^1/\ell^2\)-minimization. We prove this by establishing an appropriate version of the restricted isometry property. Our result complements previous nonuniform recovery results in this context, and provides stronger stability guarantees for noisy measurements and approximately sparse signals. Second, we determine the minimal number of scalar-valued measurements needed to uniformly recover all fusion frame sparse signals via mixed \(\ell^1/\ell^2\)-minimization. This bound is achieved by scalar-valued subgaussian measurements. In particular, our result shows that the number of scalar-valued subgaussian measurements cannot be further reduced using knowledge of the coherence parameter. As a special case it implies that the best known uniform recovery result for block sparse signals using subgaussian measurements is optimal.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)

References:

[1] Alltop, W., Complex sequences with low periodic correlations, IEEE Trans. Inform. Theory, 26, 3, 350-354 (1980) · Zbl 0432.94011
[2] Ayaz, U.; Rauhut, H., Sparse recovery with fusion frames via RIP, (Proc. SampTA (2013))
[4] Baldassarre, L.; Bhan, N.; Cevher, V.; Kyrillidis, A., Group-sparse model selection: hardness and relaxations · Zbl 1359.94943
[5] Blumensath, T., Sampling and reconstructing signals from a union of linear subspaces, IEEE Trans. Inform. Theory, 57, 7, 4660-4671 (2011) · Zbl 1365.94173
[6] Bodmann, B.; Casazza, P.; Peterson, J.; Smalyanau, I.; Tremain, J., Fusion frames and unbiased basic sequences, (Andrews, T. D.; Balan, R.; Benedetto, J. J.; Czaja, W.; Okoudjou, K. A., Excursions in Harmonic Analysis. Excursions in Harmonic Analysis, Applied and Numerical Harmonic Analysis, vol. 1 (2013), Birkhäuser: Birkhäuser Boston), 19-34 · Zbl 1317.42024
[7] Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities: A Nonasymptotic Theory of Independence (2013), Oxford University Press · Zbl 1279.60005
[8] Boufounos, P.; Kutyniok, G.; Rauhut, H., Sparse recovery from combined fusion frame measurements, IEEE Trans. Inform. Theory, 57, 6, 3864-3876 (2011) · Zbl 1365.94066
[9] Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[10] Candès, E.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033
[11] Casazza, P.; Kutyniok, G., Frames of subspaces, (Wavelets, Frames and Operator Theory (2004)), 87-113 · Zbl 1058.42019
[12] Casazza, P.; Kutyniok, G., Fusion Frames, Applied and Numerical Harmonic Analysis, vol. xvi (2013), Birkhäuser: Birkhäuser Boston, MA · Zbl 1261.42048
[13] Christensen, O., An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis (2003), Birkhäuser · Zbl 1017.42022
[14] Conway, J.; Hardin, R.; Sloane, N., Packing lines, planes, etc.: packings in Grassmannian spaces, Exp. Math., 5, 2, 139-159 (1996) · Zbl 0864.51012
[15] Dhillon, I.; Heath, R.; Strohmer, T.; Tropp, J., Constructing packings in Grassmannian manifolds via alternating projection, Exp. Math., 17, 1, 9-35 (2008) · Zbl 1155.52304
[16] Dirksen, S., Dimensionality reduction with subgaussian matrices: a unified theory, Found. Comput. Math. (2016), in press · Zbl 1360.60031
[17] Dirksen, S., Tail bounds via generic chaining, Electron. J. Probab., 20, 53, 1-29 (2015) · Zbl 1327.60048
[18] Donoho, D., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[19] Donoho, D. L.; Stark, P. B., Uncertainty principles and signal recovery, SIAM J. Appl. Math., 49, 3, 906-931 (1989) · Zbl 0689.42001
[20] Eldar, Y.; Bölcskei, H., Block-sparsity: coherence and efficient recovery, (ICASSP (2009), IEEE), 2885-2888
[21] Eldar, Y.; Kuppinger, P.; Bölcskei, H., Block-sparse signals: uncertainty relations and efficient recovery, IEEE Trans. Signal Process., 58, 6, 3042-3054 (2010) · Zbl 1392.94195
[22] Eldar, Y.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press
[23] Eldar, Y.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087
[24] Eldar, Y.; Rauhut, H., Average case analysis of multichannel sparse recovery using convex relaxation, IEEE Trans. Inform. Theory, 56, 1, 505-519 (2010) · Zbl 1366.94095
[25] Fickus, M.; Mixon, D. G., Tables of the existence of equiangular tight frames (2015)
[26] Fornasier, M.; Rauhut, H., Recovery algorithms for vector valued data with joint sparsity constraints, SIAM J. Numer. Anal., 46, 2, 577-613 (2008) · Zbl 1211.65066
[27] Foucart, S.; Pajor, A.; Rauhut, H.; Ullrich, T., The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), J. Complexity, 26, 629-640 (2010) · Zbl 1204.41019
[28] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), Birkhäuser: Birkhäuser Boston · Zbl 1315.94002
[29] Fuchs, W., On the magnitude of Fourier transforms, (Proc. Int. Math. Cong.. Proc. Int. Math. Cong., Amsterdam (1954)), 106-107
[30] Gilbert, E., A comparison of signalling alphabets, Bell Syst. Tech. J., 31, 504-522 (1952)
[31] Gribonval, R.; Rauhut, H.; Schnass, K.; Vandergheynst, P., Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms, J. Fourier Anal. Appl., 14, 5, 655-687 (2008) · Zbl 1181.94045
[32] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 3, 1548-1566 (2011) · Zbl 1366.94103
[33] Krahmer, F.; Mendelson, S.; Rauhut, H., Suprema of chaos processes and the restricted isometry property, Comm. Pure Appl. Math., 67, 11, 1877-1904 (2014) · Zbl 1310.94024
[34] Kutyniok, G.; Pezeshki, A.; Calderbank, R.; Liu, T., Robust dimension reduction, fusion frames, and Grassmannian packings, Appl. Comput. Harmon. Anal., 26, 1, 64-76 (2009) · Zbl 1283.42046
[35] Ledoux, M.; Talagrand, M., Probability in Banach Spaces (1991), Springer-Verlag: Springer-Verlag Berlin · Zbl 0662.60008
[36] Lemmens, P.; Seidel, J., Equi-isoclinic subspaces of Euclidean spaces, Nederl. Akad. Wetensch. Proc. Ser. A, 76, 98-107 (1973) · Zbl 0272.50008
[37] Mendelson, S.; Pajor, A.; Tomczak Jaegermann, N., Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constr. Approx., 28, 3, 277-289 (2009) · Zbl 1230.46011
[38] Pajor, A.; Tomczak-Jaegermann, N., Subspaces of small codimension of finite-dimensional Banach spaces, Proc. Amer. Math. Soc., 97, 4, 637-642 (1986) · Zbl 0623.46008
[39] Pisier, G., The Volume of Convex Bodies and Banach Space Geometry (1999), Cambridge University Press · Zbl 0933.46013
[40] Rao, N.; Recht, B.; Nowak, R., Universal measurement bounds for structured sparse signal recovery, J. Mach. Learn. Res., 22, 942-950 (2012)
[41] Redmond, D. J., Existence and construction of real-valued equiangular tight frames (2009), PhD thesis
[42] Stewart, G., Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev., 15, 727-764 (1973) · Zbl 0297.65030
[43] Stojnic, M., Block-length dependent thresholds in block-sparse compressed sensing (2009)
[44] Sustik, M. A.; Tropp, J. A.; Dhillon, I. S.; Heat, R. W., On the existence of equiangular tight frames, Linear Algebra Appl., 426, 2-3, 619-635 (2007) · Zbl 1127.15013
[45] Talagrand, M., The Generic Chaining (2005), Springer-Verlag: Springer-Verlag Berlin · Zbl 1075.60001
[46] Talagrand, M., Upper and Lower Bounds for Stochastic Processes (2014), Springer: Springer Heidelberg · Zbl 1293.60001
[48] Tropp, J., Algorithms for simultaneous sparse approximation: part II: convex relaxation, Signal Process., 86, 3, 589-602 (2006) · Zbl 1163.94395
[49] Varshamov, R., Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk SSSR, 117, 739-741 (1952) · Zbl 0081.36905
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.