Topics: Laplacian Eigenmaps, Orthogonal Polynomials, Quantum Information
Participants: Farabie Akanda; Haverford College
Elijah Anderson; Wesleyan University
Elizabeth Athaide; Massachusetts Institute of Technology
Faye Castro; Texas State University
Sara Costa; University of Hartford
Leia Donaway; Swarthmore College
Hank Ewing; Appalachian State University
Caleb Findley; University of Texas at Arlington
August Noë; University of California Santa Cruz
Sam Trombone; Hamilton College
Kai Zuang; Brown University
and
John Ackerman; UConn
Mentors: Bernard Akwei, Rachel Bailey, Maxim Derevyagin, Luke Rogers, Alexander Teplyaev
REU participants:
Bobita Atkins, Massachusetts College of Liberal Arts
Ashka Dalal, Rose-Hulman Institute of Technology
Natalie Dinin, California State University, Chico
Jonathan Kerby-White, Indiana University Bloomington
Tess McGuinness, University of Connecticut
Tonya Patricks, University of Central Florida
Genevieve Romanelli, Tufts University
Yiheng Su, Colby College
Mentors: Bernard Akwei, Rachel Bailey, Luke Rogers, Alexander Teplyaev
Convergence, optimization and stabilization of singular eigenmaps
Eigenmaps are important in analysis, geometry and machine learning, especially in nonlinear dimension reduction.
Versions of the Laplacian eigenmaps of Belkin and Niyogi are a widely used nonlinear dimension reduction technique in data analysis. Data points in a high dimensional space \(\mathbb{R}^N\) are treated as vertices of a graph, for example by taking edges between points separated by distance at most a threshold \(\epsilon\) or by joining each vertex to its \(k\) nearest neighbors. A small number \(D\) of eigenfunctions of the graph Laplacian are then taken as coordinates for the data, defining an eigenmap to \(\mathbb{R}^D\). This method was motivated by an intuitive argument suggesting that if the original data consisted of \(n\) sufficiently well-distributed points on a nice manifold \(M\) then the eigenmap would preserve geometric features of \(M\).
Several authors have developed rigorous results on the geometric properties of eigenmaps, using a number of different assumptions on the manner in which the points are distributed, as well as hypotheses involving, for example, the smoothness of the manifold and bounds on its curvature. Typically, they use the idea that under smoothness and curvature assumptions one can approximate the Laplace-Beltrami operator of \(M\) by an operator giving the difference of the function value and its average over balls of a sufficiently small size \(\epsilon\), and that this difference operator can be approximated by graph Laplacian operators provided that the \(n\) points are sufficiently well distributed.
In the present work we consider several model situations where eigen-coordinates can be computed analytically as well as numerically, including the intervals with uniform and weighted measures, square, torus, sphere, and the Sierpinski gasket. On these examples we investigate the connections between eigenmaps and orthogonal polynomials, how to determine the optimal value of \(\epsilon\) for a given \(n\) and prescribed point distribution, and the dependence and stability of the method when the choice of Laplacian is varied. These examples are intended to serve as model cases for later research on the corresponding problems for eigenmaps on weighted Riemannian manifolds, possibly with boundary, and on some metric measure spaces, including fractals.
Approximation of the eigenmaps of a Laplace operator depends crucially on the scaling parameter \(\epsilon\). If \(\epsilon\) is too small or too large, then the approximation is inaccurate or completely breaks down. However, an analytic expression for the optimal \(\epsilon\) is out of reach. In our work, we use some explicitly solvable models and Monte Carlo simulations to find the approximately optimal value of \(\epsilon\) that gives, on average, the most accurate approximation of the eigenmaps.
Our study is primarily inspired by the work of Belkin and Niyogi “Towards a theoretical foundation for Laplacian-based manifold methods.”
Results are presented at the 2023 Young Mathematicians Conference (YMC) at the Ohio State University, a premier annual conference for undergraduate research in mathematics, and at the 2024 Joint Mathematics Meetings (JMM) in San Francisco, the largest mathematics gathering in the world.
Bobita Atkins
Ashka Dalal
Natalie Dinin
Jonathan Kerby-White
Tess Mcguinness
Tonya Patricks
Genevieve Romanelli
Yiheng Su
Working with Professor Sasha Teplyaev
Yiheng and Jonathan share their results.
Vievie and Tonya present their work.
Bobita, Ashka, and Natalie explain random eigencoordinates.
Geodesics (shortest paths) on manifolds such as planes and spheres are well understood. Geodesics on fractal sets such as the Sierpinski Triangle are much more complicated. We begin by constructing algorithms for building shortest paths and provide explicit formulas for computing their lengths. We then turn to the question of interpolation along geodesics—given two subsets of the Sierpinski Triangle, we “slide” points in one set along geodesics to the other set. We construct a measure along the interpolated sets which formalizes a notion of the interpolation of a distribution of mass, and we prove interesting self-similarity relations about this measure.
Laplacians have been well studied on post-critically finite (PCF) fractals. However, less is known about gradients on such fractals. Building on work by Teplyaev, we generalize results regarding the existence and continuity of the gradient on the standard Sierpinski Gasket to higher dimensional Sierpinski Gaskets. In particular, we find that, for functions with a continuous Laplacian, the gradient must be defined almost everywhere, and specify a set of points for which it is defined. Furthermore, we provide a counterexample on higher-dimensional Sierpinski gaskets where the Laplacian is continuous but the gradient is not defined everywhere. We conjecture that Hölder continuity of the Laplacian is a condition strong enough to guarantee that the gradient exists at each point.
The diamond fractal is a fractal that is obtained in the following manner. Start with a graph with two vertices and an edge and replace the edge with two new vertices connected to our original vertices to obtain a diamond shaped graph. The diamond fractal is defined to be the limiting object after continuing with the edge replacement indefinitely. In the project, the spectrum of magnetic Laplacian operators on graph approximations to the diamond fractal was computed.
Given a level n approximation to the fractal with known magnetic field strengths through cells and holes, it is possible to determine the net magnetic field through the cells and holes of the preceding graph approximations. The spectral similarity relation between the operators on successive graph approximations was worked out, with the corresponding spectral decimation polynomial depending on the magnetic field strengths. A poster and talk on this work was presented at the REU Mini-Symposium at UConn.
