Steiner equiangular tight frames. (English) Zbl 1252.42032
This paper presents a construction principle for families of equiangular tight frames. These families of vectors in finite-dimensional real or complex Hilbert spaces have desirable properties for representing vectors in terms of their frame coefficients: Up to an overall multiplicative constant, the map from a vector to its frame coefficients, its inner products with the frame vectors, is an isometry; the norms of the frame vectors are equal and the inner product of any pair of vectors is a fixed constant. The interplay between these requirements has given rise to many papers on possible construction methods, including fundamental combinatorial techniques by Seidel and collaborators.
The present paper builds on Seidel’s insight that equiangular tight frames are in the real case representatives of switching equivalence classes [J. J. Seidel, in: Colloq. int. Teorie comb., Roma 1973, Tomo I, 481–511 (1976; Zbl 0352.05016)]. These switching equivalence classes can be identified with regular two-graphs. The paper demonstrates that the construction of regular two-graphs is related to a type of Steiner system, and that this relationship and the associated construction method generalize painlessly to the complex case.
An additional topic that is examined is the question whether equiangular tight frames are good candidates for matrices with the restricted isometry property, or whether they have an intrinsic scaling property as in the construction by R. A. DeVore [J. Complexity 23, No. 4–6, 918–925 (2007; Zbl 1134.94312)] that makes them inferior to random families. At least for the type of frames examined here it turns out that the usual estimates for the restricted isometry constant cannot be improved further. This implies that equiangular tight frames constructed with Steiner systems are inferior to randomized constructions or to the recent deterministic construction by [J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, Duke Math. J. 159, No. 1, 145–185 (2011; Zbl 1236.94027)]. This leaves the question open whether there are other construction principles for equiangular tight frames that lead to better restricted isometry constants.
The present paper builds on Seidel’s insight that equiangular tight frames are in the real case representatives of switching equivalence classes [J. J. Seidel, in: Colloq. int. Teorie comb., Roma 1973, Tomo I, 481–511 (1976; Zbl 0352.05016)]. These switching equivalence classes can be identified with regular two-graphs. The paper demonstrates that the construction of regular two-graphs is related to a type of Steiner system, and that this relationship and the associated construction method generalize painlessly to the complex case.
An additional topic that is examined is the question whether equiangular tight frames are good candidates for matrices with the restricted isometry property, or whether they have an intrinsic scaling property as in the construction by R. A. DeVore [J. Complexity 23, No. 4–6, 918–925 (2007; Zbl 1134.94312)] that makes them inferior to random families. At least for the type of frames examined here it turns out that the usual estimates for the restricted isometry constant cannot be improved further. This implies that equiangular tight frames constructed with Steiner systems are inferior to randomized constructions or to the recent deterministic construction by [J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova, Duke Math. J. 159, No. 1, 145–185 (2011; Zbl 1236.94027)]. This leaves the question open whether there are other construction principles for equiangular tight frames that lead to better restricted isometry constants.
Reviewer: Bernhard Bodmann (Houston)
References:
| [1] | Abel, R. J.R.; Greig, M., BIBDs with small block size, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs (2007), Chapman and Hall/CRC), 72-79 · Zbl 0881.05019 |
| [2] | Appleby, D. M., Symmetric informationally complete-positive operator valued measures and the extended Clifford group, J. Math. Phys., 46, 052107-1-052107-29 (2005) · Zbl 1110.81023 |
| [3] | Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 253-263 (2008) · Zbl 1177.15015 |
| [4] | Bodmann, B. G.; Elwood, H. J., Complex equiangular Parseval frames and Seidel matrices containing \(p\) th roots of unity, Proc. Amer. Math. Soc., 138, 4387-4404 (2010) · Zbl 1209.42020 |
| [5] | Bodmann, B. G.; Paulsen, V. I., Frames, graphs and erasures, Linear Algebra Appl., 404, 118-146 (2005) · Zbl 1088.46009 |
| [6] | Bodmann, B. G.; Paulsen, V. I.; Tomforde, M., Equiangular tight frames from complex Seidel matrices containing cube roots of unity, Linear Algebra Appl., 430, 396-417 (2009) · Zbl 1165.42007 |
| [7] | Bourgain, J.; Dilworth, S. J.; Ford, K.; Konyagin, S.; Kutzarova, D., Explicit constructions of RIP matrices and related problems, Duke Math. J., 159, 145-185 (2011) · Zbl 1236.94027 |
| [8] | Brouwer, A. E., Strongly regular graphs, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs (2007), Chapman and Hall/CRC), 852-868 · Zbl 1110.05320 |
| [9] | Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 4203-4215 (2005) · Zbl 1264.94121 |
| [10] | Candès, E. J.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 5406-5425 (2006) · Zbl 1309.94033 |
| [11] | Casazza, P. G.; Fickus, M.; Mixon, D.; Wang, Y.; Zhou, Z., Constructing tight fusion frames, Appl. Comput. Harmon. Anal., 30, 175-187 (2011) · Zbl 1221.42052 |
| [12] | P.G. Casazza, A. Heinecke, F. Krahmer, G. Kutyniok, Optimally sparse frames, preprint.; P.G. Casazza, A. Heinecke, F. Krahmer, G. Kutyniok, Optimally sparse frames, preprint. · Zbl 1365.94059 |
| [13] | P.G. Casazza, D. Redmond, J.C. Tremain, Real equiangular frames, in: Proc. Conf. Inf. Sci. Syst., 2008, pp. 715-720.; P.G. Casazza, D. Redmond, J.C. Tremain, Real equiangular frames, in: Proc. Conf. Inf. Sci. Syst., 2008, pp. 715-720. |
| [14] | Colbourn, C. J.; Mathon, R., Steiner systems, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs (2007), Chapman and Hall/CRC), 102-110 · Zbl 1101.05001 |
| [15] | DeVore, R. A., Deterministic constructions of compressed sensing matrices, J. Complexity, 23, 918-925 (2007) · Zbl 1134.94312 |
| [16] | Duncan, D. M.; Hoffman, T. R.; Solazzo, J. P., Equiangular tight frames and fourth root seidel matrices, Linear Algebra Appl., 432, 2816-2823 (2010) · Zbl 1223.05172 |
| [17] | Fickus, M., Maximally equiangular frames and Gauss sums, J. Fourier Anal. Appl., 15, 413-427 (2009) · Zbl 1247.42027 |
| [18] | Holmes, R. B.; Paulsen, V. I., Optimal frames for erasures, Linear Algebra Appl., 377, 31-51 (2004) · Zbl 1042.46009 |
| [19] | Kalra, D., Complex equiangular cyclic frames and erasures, Linear Algebra Appl., 419, 373-399 (2006) · Zbl 1119.42013 |
| [20] | Khatirinejad, M., On Weyl-Heisenberg orbits of equiangular lines, J. Algebraic Combin., 28, 333-349 (2008) · Zbl 1200.05032 |
| [21] | Lemmens, P. W.H.; Seidel, J. J., Equiangular lines, J. Algebra, 24, 494-512 (1973) · Zbl 0255.50005 |
| [22] | Nelson, J. L.; Temlyakov, V. N., On the size of incoherent systems, J. Approx. Theory, 163, 1238-1245 (2011) · Zbl 1242.41037 |
| [23] | Renes, J. M., Equiangular tight frames from Paley tournaments, Linear Algebra Appl., 426, 497-501 (2007) · Zbl 1127.05019 |
| [24] | Renes, J. M.; Blume-Kohout, R.; Scott, A. J.; Caves, C. M., Symmetric informationally complete quantum measurements, J. Math. Phys., 45, 2171-2180 (2004) · Zbl 1071.81015 |
| [25] | Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Anal., 61, 1025-1045 (2008) · Zbl 1149.94010 |
| [26] | Scott, A. J.; Grassl, M., Symmetric informationally complete positive-operator valued measures: a new computer study, J. Math. Phys., 51, 042203-1-042203-15 (2010) · Zbl 1310.81022 |
| [27] | J.J. Seidel, A survey of two-graphs, in: Proc. Intern. Coll. Teorie Combinatorie, 1973, pp. 481-511.; J.J. Seidel, A survey of two-graphs, in: Proc. Intern. Coll. Teorie Combinatorie, 1973, pp. 481-511. · Zbl 0352.05016 |
| [28] | Singh, P., Equiangular tight frames and signature sets in groups, Linear Algebra Appl., 433, 2208-2242 (2010) · Zbl 1207.42026 |
| [29] | Strohmer, T., A note on equiangular tight frames, Linear Algebra Appl., 429, 326-330 (2008) · Zbl 1153.15003 |
| [30] | Strohmer, T.; Heath, R. W., Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal., 14, 257-275 (2003) · Zbl 1028.42020 |
| [31] | Sustik, M. A.; Tropp, J. A.; Dhillon, I. S.; Heath, R. W., On the existence of equiangular tight frames, Linear Algebra Appl., 426, 619-635 (2007) · Zbl 1127.15013 |
| [32] | Tropp, J. A.; Dhillon, I. S.; Heath, R. W.; Strohmer, T., Designing structured tight frames via an alternating projection method, IEEE Trans. Inform. Theory, 51, 188-209 (2005) · Zbl 1288.94021 |
| [33] | Waldron, S., On the construction of equiangular frames from graphs, Linear Algebra Appl., 431, 2228-2242 (2009) · Zbl 1216.05079 |
| [34] | Xia, P.; Zhou, S.; Giannakis, G. B., Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory, 51, 1900-1907 (2005) · Zbl 1237.94007 |
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.
