nach oben

Designs, Codes and Cryptography

Erschienen in:

09.10.2018

Equiangular tight frames from group divisible designs

verfasst von: Matthew Fickus, John Jasper

Erschienen in: Designs, Codes and Cryptography | Ausgabe 7/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An equiangular tight frame (ETF) is a type of optimal packing of lines in a real or complex Hilbert space. In the complex case, the existence of an ETF of a given size remains an open problem in many cases. In this paper, we observe that many of the known constructions of ETFs are of one of two types. We further provide a new method for combining a given ETF of one of these two types with an appropriate group divisible design (GDD) in order to produce a larger ETF of the same type. By applying this method to known families of ETFs and GDDs, we obtain several new infinite families of ETFs. The real instances of these ETFs correspond to several new infinite families of strongly regular graphs. Our approach was inspired by a seminal paper of Davis and Jedwab which both unified and generalized McFarland and Spence difference sets. Our main result is a combinatorial analog of their algebraic results.

Vorheriger Artikel Factorization of a class of composed polynomials

Nächster Artikel Maximal contrast color visual secret sharing schemes

Abel R.J.R., Greig M.: BIBDs with small block size. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 72–79. CRC Press, Boca Raton (2007).

Abel R.J.R., Colbourn C.J., Dinitz J.H.: Mutually orthogonal Latin squares (MOLS). In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 160–193. CRC Press, Boca Raton (2007).

Azarija J., Marc T.: There is no (75,32,10,16) strongly regular graph. arXiv:1509.05933.

Azarija J., Marc T.: There is no (95,40,12,20) strongly regular graph. arXiv:1603.02032.

Bajwa W.U., Calderbank R., Mixon D.G.: Two are better than one: fundamental parameters of frame coherence. Appl. Comput. Harmon. Anal. 33, 58–78 (2012).MathSciNetCrossRefMATH

Bandeira A.S., Fickus M., Mixon D.G., Wong P.: The road to deterministic matrices with the Restricted Isometry Property. J. Fourier Anal. Appl. 19, 1123–1149 (2013).MathSciNetCrossRefMATH

Barg A., Glazyrin A., Okoudjou K.A., Yu W.-H.: Finite two-distance tight frames. Linear Algebra Appl. 475, 163–175 (2015).MathSciNetCrossRefMATH

Bodmann B.G., Elwood H.J.: Complex equiangular Parseval frames and Seidel matrices containing \(p\)th roots of unity. Proc. Am. Math. Soc. 138, 4387–4404 (2010).CrossRefMATH

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).MathSciNetCrossRefMATH

10.

Bracken C., McGuire G., Ward H.: New quasi-symmetric designs constructed using mutually orthogonal Latin squares and Hadamard matrices. Des. Codes Cryptogr. 41, 195–198 (2006).MathSciNetCrossRefMATH

11.

Brouwer A.E.: Strongly regular graphs. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 852–868. CRC Press, Boca Raton (2007).

12.

Brouwer A.E.: Parameters of strongly regular graphs. http://www.win.tue.nl/~aeb/graphs/srg/.

13.

Chang K.I.: An existence theory for group divisible designs. Ph.D. Thesis, The Ohio State University (1976).

14.

Chen Y.Q.: On the existence of abelian Hadamard difference sets and a new family of difference sets. Finite Fields Appl. 3, 234–256 (1997).MathSciNetCrossRefMATH

15.

Corneil D., Mathon R. (eds.): Geometry and Combinatorics: Selected Works of J. J. Seidel. Academic Press, New York (1991).

16.

Coutinho G., Godsil C., Shirazi H., Zhan H.: Equiangular lines and covers of the complete graph. Linear Algebra Appl. 488, 264–283 (2016).MathSciNetCrossRefMATH

17.

Davis J.A., Jedwab J.: A unifying construction for difference sets. J. Comb. Theory Ser. A 80, 13–78 (1997).MathSciNetCrossRefMATH

18.

Ding C., Feng T.: A generic construction of complex codebooks meeting the Welch bound. IEEE Trans. Inf. Theory 53, 4245–4250 (2007).MathSciNetCrossRefMATH

19.

Fickus M., Mixon D.G.: Tables of the existence of equiangular tight frames. arXiv:1504.00253 (2016).

20.

Fickus M., Mixon D.G., Tremain J.C.: Steiner equiangular tight frames. Linear Algebra Appl. 436, 1014–1027 (2012).MathSciNetCrossRefMATH

21.

Fickus M., Mixon D.G., Jasper J.: Equiangular tight frames from hyperovals. IEEE Trans. Inf. Theory 62, 5225–5236 (2016).MathSciNetCrossRefMATH

22.

Fickus M., Jasper J., Mixon D.G., Peterson J.D.: Tremain equiangular tight frames. J. Comb. Theory Ser. A 153, 54–66 (2018).MathSciNetCrossRefMATH

23.

Fickus M., Jasper J., Mixon D.G., Peterson J.D.: Hadamard equiangular tight frames. arXiv:1703.05353.

24.

Fickus M., Jasper J., Mixon D.G., Peterson J.D., Watson C.E.: Equiangular tight frames with centroidal symmetry. Appl. Comput. Harmon. Anal. (to appear).

25.

Fickus M., Jasper J., Mixon D.G., Peterson J.D., Watson C.E.: Polyphase equiangular tight frames and abelian generalized quadrangles. Appl. Comput. Harmon. Anal. (to appear).

26.

Fuchs C.A., Hoang M.C., Stacey B.C.: The SIC question: history and state of play. Axioms 6, 21 (2017).CrossRef

27.

Ge G.: Group divisible designs. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 255–260. CRC Press, Boca Raton (2007).

28.

Godsil C.D.: Krein covers of complete graphs. Aust. J. Comb. 6, 245–255 (1992).MathSciNetMATH

29.

Goethals J.M., Seidel J.J.: Strongly regular graphs derived from combinatorial designs. Can. J. Math. 22, 597–614 (1970).MathSciNetCrossRefMATH

30.

Gordon D.: La Jolla covering repository. https://www.ccrwest.org/diffsets.html.

31.

Grassl M., Scott A.J.: Fibonacci-Lucas SIC-POVMs. J. Math. Phys. 58, 122201 (2017).MathSciNetCrossRefMATH

32.

Holmes R.B., Paulsen V.I.: Optimal frames for erasures. Linear Algebra Appl. 377, 31–51 (2004).MathSciNetCrossRefMATH

33.

Iverson J.W., Jasper J., Mixon D.G.: Optimal line packings from nonabelian groups. arXiv:1609.09836.

34.

Jasper J., Mixon D.G., Fickus M.: Kirkman equiangular tight frames and codes. IEEE Trans. Inf. Theory 60, 170–181 (2014).MathSciNetCrossRefMATH

35.

Jungnickel D., Pott A., Smith K.W.: Difference sets. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 419–435. CRC Press, Boca Raton (2007).

36.

Lamken E.R., Wilson R.M.: Decompositions of edge-colored complete graphs. J. Comb. Theory Ser. A 89, 149–200 (2000).MathSciNetCrossRefMATH

37.

Lemmens P.W.H., Seidel J.J.: Equiangular lines. J. Algebra 24, 494–512 (1973).MathSciNetCrossRefMATH

38.

Mathon R., Rosa A.: \(2-(v, k,\lambda )\) designs of small order. In: Colbourn C.J., Dinitz J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn, pp. 25–58. CRC Press, Boca Raton (2007).

39.

MacNeish H.F.: Euler squares. Ann. Math. 23, 221–227 (1922).MathSciNetCrossRefMATH

40.

McFarland R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15, 1–10 (1973).MathSciNetCrossRefMATH

41.

McGuire G.: Quasi-symmetric designs and codes meeting the Grey-Rankin bound. J. Comb. Theory Ser. A 78, 280–291 (1997).MathSciNetCrossRefMATH

42.

Mohácsy H.: The asymptotic existence of group divisible designs of large order with index one. J. Comb. Theory Ser. A 118, 1915–1924 (2011).MathSciNetCrossRefMATH

43.

Renes J.M.: Equiangular tight frames from Paley tournaments. Linear Algebra Appl. 426, 497–501 (2007).MathSciNetCrossRefMATH

44.

Renes J.M., Blume-Kohout R., Scott A.J., Caves C.M.: Symmetric informationally complete quantum measurements. J. Math. Phys. 45, 2171–2180 (2004).MathSciNetCrossRefMATH

45.

Seidel J.J.: A survey of two-graphs. Coll. Int. Teorie Combin., Atti dei Convegni Lincei, vol. 17, pp. 481–511. Accademia Nazionale dei Lincei, Rome (1976).

46.

Spence E.: A family of difference sets. J. Comb. Theory Ser. A 22, 103–106 (1977).MathSciNetCrossRefMATH

47.

Strohmer T.: A note on equiangular tight frames. Linear Algebra Appl. 429, 326–330 (2008).MathSciNetCrossRefMATH

48.

Strohmer T., Heath R.W.: Grassmannian frames with applications to coding and communication. Appl. Comput. Harmon. Anal. 14, 257–275 (2003).MathSciNetCrossRefMATH

49.

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).MathSciNetCrossRefMATH

50.

Szöllősi F.: All complex equiangular tight frames in dimension 3. arXiv:1402.6429.

51.

Tropp J.A.: Complex equiangular tight frames. Proc. SPIE 5914, 591401/1–11 (2005).

52.

Tropp J.A., Dhillon I.S., Heath Jr. R.W., Strohmer T.: Designing structured tight frames via an alternating projection method. IEEE Trans. Inf. Theory 51, 188–209 (2005).MathSciNetCrossRefMATH

53.

Turyn R.J.: Character sums and difference sets. Pac. J. Math. 15, 319–346 (1965).MathSciNetCrossRefMATH

54.

van Lint J.H., Seidel J.J.: Equilateral point sets in elliptic geometry. Indag. Math. 28, 335–348 (1966).MathSciNetCrossRefMATH

55.

Waldron S.: On the construction of equiangular frames from graphs. Linear Algebra Appl. 431, 2228–2242 (2009).MathSciNetCrossRefMATH

56.

Welch L.R.: Lower bounds on the maximum cross correlation of signals. IEEE Trans. Inf. Theory 20, 397–399 (1974).CrossRefMATH

57.

Wilson R.M.: An existence theory for pairwise balanced designs I. Composition theorems and morphisms. J. Comb. Theory Ser. A 13, 220–245 (1972).MathSciNetCrossRefMATH

58.

Xia P., Zhou S., Giannakis G.B.: Achieving the Welch bound with difference sets. IEEE Trans. Inf. Theory 51, 1900–1907 (2005).MathSciNetCrossRefMATH

59.

Zauner G.: Quantum designs: foundations of a noncommutative design theory. Ph.D. Thesis, University of Vienna (1999).

Titel: Equiangular tight frames from group divisible designs
verfasst von: Matthew Fickus
John Jasper
Publikationsdatum: 09.10.2018
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 7/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0569-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 7/2019

On existence theorems for simple t-designs

A new family of partial difference sets in 3-groups

Maximal contrast color visual secret sharing schemes

Erasure combinatorial batch codes based on nonadaptive group testing

Optimal 2-D -optical orthogonal codes and related equi-difference conflict avoiding codes

Variations of the Primitive Normal Basis Theorem