Least distortion Euclidean embeddings of flat tori
Pages 13 - 23
Abstract
Lattices (discrete subgroups of n-dimensional Euclidean spaces) are ubiquitous objects in mathematics.
One typical algorithmic problem for lattices is the closest vector problem (given a lattice and a point in Euclidean space, which lattice vector is closest to this given point?). In general the closest vector problem is NP-hard. One potential approach to derive efficient approximation algorithm for the closest vector problem could go via the concept of least distortion metric embeddings.
In this paper we derive and analyze an infinite-dimensional semidefinite program which computes least distortion embeddings of flat tori, where L is an n-dimensional lattice, into Hilbert spaces. This enables us to derive some optimal embeddings of flat tori given by certain important lattices, especially of the hexagonal lattice A2 and the root lattice E8. For this we apply and modify the linear programming method for spherical designs.
References
[1]
[1] S. Arora, J.R. Lee, A. Naor, Euclidean distortion and the sparsest cut, J. Amer. Math. Soc. 21 (2008), 1–21.
[2]
[2] I. Agarwal, O. Regev, Y. Tang, Nearly optimal embeddings of flat tori, APPROX/RANDOM 2020.
[3]
[3] G.E. Andrews, R. Askey, and R. Roy, Special Functions, Encyclopedia of Mathematics and its Applications 71, Cambridge University Press, Cambridge, 1999.
[4]
[4] C. Bachoc, D.C. Gijswijt, A. Schrijver, F. Vallentin, Invariant semidefinite programs, pp. 219–269 in: Handbook on semidefinite, conic, and polynomial optimization (M.F. Anjos, J.B. Lasserre, eds.), Springer, 2012.
[5]
[5] S. Borodachov, Min-Max Polarization for Certain Classes of Sharp Configurations on the Sphere, arXiv:2203.13756 [math.CA]
[6]
[6] P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, M. Stoyanova, On polarization of spherical codes and designs, J. Math. Anal. Appl. 524 (2023), Paper No. 127065, 29 pp.
[7]
[7] G.J. Butler, Simultaneous packing and covering in Euclidean space, Proc. London Math. Soc. 25 (1972) 721–735.
[8]
[8] S.M. Cioabă, H. Gupta, F. Ihringer, H. Kurihara, The least Euclidean distortion constant of a distance-regular graph, Discrete Applied Mathematics 325 (2023), 212–225.
[9]
[9] H. Cohn, A. Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc. 20 (2007), 99–148.
[10]
[10] J.H. Conway, N.J.A. Sloane, Sphere packings, lattices, and groups, Springer, 1988.
[11]
[11] P.J. Davis, Interpolation and Approximation, Blaisdell Publishing Company, New York, 1963.
[12]
[12] P. Delsarte, J.M. Goethals, J.J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), 363–388.
[13]
[13] G. Fazekas, V.I Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces, Journal of Combinatorial Theory, Series A 70 (1995) 267–288.
[14]
[14] G.B. Folland, A course in abstract harmonic analysis, CRC Press, 1995.
[15]
[15] M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988.
[16]
[16] I. Haviv, O. Regev, The Euclidean distortion of flat tori, J. Topol. Anal. 5 (2013), 205–223 (extended abstract appeared in APPROX/RANDOM 2010).
[17]
[17] A. Heimendahl, M. Lücke, F. Vallentin, M.C. Zimmermann, A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces, arXiv, 2022.
[18]
[18] S. Khot, A. Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006), 821–852 (extended abstract appeared in FOCS 2005)
[19]
[19] E. de Klerk, F. Vallentin, On the Turing model complexity of interior point methods for semidefinite programming, SIAM J. Optim. 26 (2016), 1944–1961.
[20]
[20] T. Kobayashi, T. Kondo, The Euclidean distortion of generalized polygons, Adv. Geom. 15 (2015), 499–506.
[21]
[21] M. Laurent, F. Vallentin, A course on semidefinite optimization, Cambridge University Press, in preparation.
[22]
[22] N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), 215–246.
[23]
[23] N. Linial, A. Magen, Least-distortion Euclidean embeddings of graphs: products of cycles and expanders, J. Combin. Theory Ser. B 79 (2000), 157–171.
[24]
[24] N. Linial, A. Magen, A. Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002), 380–394.
[25]
[25] J. Matoušek, Lectures on discrete geometry, Springer, 2002.
[26]
[26] E.H. Moore, On properly positive Hermitian matrices, Bull. Amer. Math. Soc. 23 (1916), 66–67.
[27]
[27] F. Vallentin, Optimal distortion embeddings of distance regular graphs into Euclidean spaces, J. Combin. Theory Ser. B 98 (2008), 95–104.
[28]
[28] V.A. Yudin, Covering a sphere and extremal properties of orthogonal polynomials, Discrete Math. Appl. 5 (1995), 371–379.
Recommendations
The Euclidean distortion of flat tori
APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniquesWe show that for every n-dimensional lattice L the torus Rn/L can be embedded with distortion O(nċ√logn) into a Hilbert space. This improves the exponential upper bound of O(n3n/2) due to Khot and Naor (FOCS 2005, Math. Annal. 2006) and gets close to ...
Least-Distortion Euclidean Embeddings of Graphs
Embeddings of finite metric spaces into Euclidean space have been studied in several contexts: The local theory of Banach spaces, the design of approximation algorithms, and graph theory. The emphasis is usually on embeddings with the least possible ...
Optimal distortion embeddings of distance regular graphs into Euclidean spaces
In this paper we give a lower bound for the least distortion embedding of a distance regular graph into Euclidean space. We use the lower bound for finding the least distortion for Hamming graphs, Johnson graphs, and all strongly regular graphs. Our ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
567 pages
Copyright © 2023 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Qualifiers
- Invited-talk
- Research
- Refereed limited
Conference
ISSAC 2023
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023
July 24 - 27, 2023
Tromsø, Norway
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 41Total Downloads
- Downloads (Last 12 months)14
- Downloads (Last 6 weeks)1
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format