Document Open Access Logo

Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction

Authors Luis Scoccola , Hitesh Gakhar , Johnathan Bush , Nikolas Schonsheck , Tatum Rask, Ling Zhou , Jose A. Perea

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.57.pdf
  • Filesize: 6.57 MB
  • 20 pages

Document Identifiers

Author Details

Luis Scoccola
  • Department of Mathematics, Northeastern University, Boston, MA, USA
Hitesh Gakhar
  • Department of Mathematics, The University of Oklahoma, Norman, OK, USA
Johnathan Bush
  • Department of Mathematics, University of Florida, Gainesville, FL, USA
Nikolas Schonsheck
  • Department of Mathematical Sciences, University of Delaware, Newark, DE, USA
Tatum Rask
  • Department of Mathematics, Colorado State University, Fort Collins, CO, USA
Ling Zhou
  • Department of Mathematics, The Ohio State University, Columbus, OH, USA
Jose A. Perea
  • Department of Mathematics and Khoury College of Computer Sciences, Northeastern University, Boston, MA, USA

Funding

This material is based upon work initiated during the 2022 Mathematics Research Community Data Science at the Crossroads of Analysis, Geometry, and Topology supported by the National Science Foundation under Grant Number DMS 1916439.
  • Scoccola, Luis: supported by the NSF through grants CCF-2006661 and CAREER award DMS-1943758.
  • Bush, Johnathan: supported by the NSF-Simons Southeast Center for Mathematics and Biology through NSF grant DMS-1764406 and Simons Foundation grant 594594.
  • Schonsheck, Nikolas: supported by the Air Force Office of Scientific Research through award number FA9550-21-1-0266.
  • Perea, Jose A.: supported by the NSF through grants CCF-2006661 and CAREER award DMS-1943758.

Cite AsGet BibTex

Luis Scoccola, Hitesh Gakhar, Johnathan Bush, Nikolas Schonsheck, Tatum Rask, Ling Zhou, and Jose A. Perea. Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.57

Abstract

The circular coordinates algorithm of de Silva, Morozov, and Vejdemo-Johansson takes as input a dataset together with a cohomology class representing a 1-dimensional hole in the data; the output is a map from the data into the circle that captures this hole, and that is of minimum energy in a suitable sense. However, when applied to several cohomology classes, the output circle-valued maps can be "geometrically correlated" even if the chosen cohomology classes are linearly independent. It is shown in the original work that less correlated maps can be obtained with suitable integer linear combinations of the cohomology classes, with the linear combinations being chosen by inspection. In this paper, we identify a formal notion of geometric correlation between circle-valued maps which, in the Riemannian manifold case, corresponds to the Dirichlet form, a bilinear form derived from the Dirichlet energy. We describe a systematic procedure for constructing low energy torus-valued maps on data, starting from a set of linearly independent cohomology classes. We showcase our procedure with computational examples. Our main algorithm is based on the Lenstra-Lenstra-Lovász algorithm from computational number theory.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
Keywords
  • dimensionality reduction
  • lattice reduction
  • Dirichlet energy
  • harmonic
  • cocycle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Miklós Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, pages 10-19, New York, NY, USA, 1998. Association for Computing Machinery. URL: https://doi.org/10.1145/276698.276705.
  2. P. Dayal and M.K. Varanasi. An algebraic family of complex lattices for fading channels with application to space-time codes. IEEE Transactions on Information Theory, 51(12):4184-4202, 2005. URL: https://doi.org/10.1109/TIT.2005.858923.
  3. Vin de Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete Comput. Geom., 45(4):737-759, 2011. URL: https://doi.org/10.1007/s00454-011-9344-x.
  4. Vin De Silva and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 227-236, 2009. Google Scholar
  5. M.E Dyer and A.M Frieze. A simple heuristic for the p-centre problem. Operations Research Letters, 3(6):285-288, 1985. URL: https://doi.org/10.1016/0167-6377(85)90002-1.
  6. Arseny Finkelstein, Dori Derdikman, Alon Rubin, Jakob N. Foerster, Liora Las, and Nachum Ulanovsky. Three-dimensional head-direction coding in the bat brain. Nature, 517(7533):159-164, 2015. URL: https://doi.org/10.1038/nature14031.
  7. Richard J Gardner, Erik Hermansen, Marius Pachitariu, Yoram Burak, Nils A Baas, Benjamin A Dunn, May-Britt Moser, and Edvard I Moser. Toroidal topology of population activity in grid cells. Nature, 602(7895):123-128, 2022. Google Scholar
  8. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. URL: https://doi.org/10.1016/0304-3975(85)90224-5.
  9. James M Hyman and Basil Nicolaenko. The Kuramoto-Sivashinsky equation: a bridge between PDE’s and dynamical systems. Physica D: Nonlinear Phenomena, 18(1-3):113-126, 1986. Google Scholar
  10. Jürgen Jost. Riemannian geometry and geometric analysis. Universitext. Springer, Cham, seventh edition, 2017. URL: https://doi.org/10.1007/978-3-319-61860-9.
  11. Louis Kang, Boyan Xu, and Dmitriy Morozov. Evaluating state space discovery by persistent cohomology in the spatial representation system. Frontiers in computational neuroscience, 15:28, 2021. Google Scholar
  12. Subhash Khot. Inapproximability results for computational problems on lattices. In The LLL Algorithm, pages 453-473. Springer, 2009. Google Scholar
  13. Yoshiki Kuramoto and Toshio Tsuzuki. Persistent propagation of concentration waves in dissipative media far from thermal equilibrium. Progress of theoretical physics, 55(2):356-369, 1976. Google Scholar
  14. Roy R. Lederman and Ronen Talmon. Learning the geometry of common latent variables using alternating-diffusion. Applied and Computational Harmonic Analysis, 44(3):509-536, 2018. URL: https://doi.org/10.1016/j.acha.2015.09.002.
  15. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515-534, 1982. URL: https://doi.org/10.1007/BF01457454.
  16. Hengrui Luo, Jisu Kim, Alice Patania, and Mikael Vejdemo-Johansson. Topological learning for motion data via mixed coordinates. In 2021 IEEE International Conference on Big Data (Big Data), pages 3853-3859, 2021. URL: https://doi.org/10.1109/BigData52589.2021.9671525.
  17. Daniel M Michelson and Gregory I Sivashinsky. Nonlinear analysis of hydrodynamic instability in laminar flames—II. numerical experiments. Acta astronautica, 4(11-12):1207-1221, 1977. Google Scholar
  18. James R. Munkres. Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984. Google Scholar
  19. Phong Q Nguên and Damien Stehlé. Floating-point LLL revisited. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 215-233. Springer, 2005. Google Scholar
  20. John O'Keefe. Place units in the hippocampus of the freely moving rat. Experimental Neurology, 51(1):78-109, 1976. URL: https://doi.org/10.1016/0014-4886(76)90055-8.
  21. Jose A Perea. Sparse circular coordinates via principal ℤ-bundles. In Topological Data Analysis, pages 435-458. Springer, 2020. Google Scholar
  22. Oded Regev. On the complexity of lattice problems with polynomial approximation factors. In The LLL algorithm, pages 475-496. Springer, 2009. Google Scholar
  23. Erik Rybakken, Nils Baas, and Benjamin Dunn. Decoding of neural data using cohomological feature extraction. Neural computation, 31(1):68-93, 2019. Google Scholar
  24. L. Scoccola, H. Gakhar, J. Bush, N. Schonsheck, T. Rask, L. Zhou, and J. A. Perea. Sparse Toroidal Coordinates. https://github.com/LuisScoccola/DREiMac, 2022.
  25. Luis Scoccola, Hitesh Gakhar, Johnathan Bush, Nikolas Schonsheck, Tatum Rask, Ling Zhou, and Jose A Perea. Toroidal coordinates: Decorrelating circular coordinates with lattice reduction. arXiv preprint arXiv:2212.07201, 2022. Google Scholar
  26. Gregory I Sivashinsky and DM Michelson. On irregular wavy flow of a liquid film down a vertical plane. Progress of theoretical physics, 63(6):2112-2114, 1980. Google Scholar
  27. Christopher Tralie, Tom Mease, and Jose Perea. DREiMac: Dimension Reduction with Eilenberg-MacLane Coordinates. https://github.com/ctralie/DREiMac, 2021.
  28. Bei Wang, Brian Summa, Valerio Pascucci, and Mikael Vejdemo-Johansson. Branching and circular features in high dimensional data. IEEE Transactions on Visualization and Computer Graphics, 17(12):1902-1911, 2011. Google Scholar
  29. Wolfram Research Inc. Mathematica, Version 13.1. Champaign, IL, 2022. URL: https://www.wolfram.com/mathematica.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact