An official website of the United States government
Given a matrix D describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of its performance on non-Euclidean metrics is lacking. In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from D, for the Frobenius norm of the difference between D and the metric Dcmds returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has a significant number of negative eigenvalues, then ∥D−Dcmds∥F, after initially decreasing, willeventually increase as we increase the dimension. Hence, counterintuitively, the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases as we increase the dimension for a variety of non-Euclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1-nearest neighbor) and complex (e.g., multi-layer neural nets) classifiers decreasing as we increase the embedding dimension.Finally, our analysis leads us to a new efficiently computable algorithm that returns a matrix Dl that is at least as close to the original distances as Dt (the Euclidean metric closest in ℓ2 distance). While Dl is not metric, when given as input to cMDS instead of D, it empirically results in solutions whose distance to D does not increase when we increase the dimension and the classification accuracy degrades less than the cMDS solution.
more »
« less
Computing a High-Dimensional Euclidean Embedding from an Arbitrary Smooth Riemannian Metric
This article presents a new method to compute a self-intersection free high-dimensional Euclidean embedding (SIFHDE^2) for surfaces and volumes equipped with an arbitrary Riemannian metric. It is already known that given a high-dimensional (high-d) embedding, one can easily compute an anisotropic Voronoi diagram by back-mapping it to 3D space. We show here how to solve the inverse problem, i.e., given an input metric, compute a smooth intersection-free high-d embedding of the input such that the pullback metric of the embedding matches the input metric. Our numerical solution mechanism matches the deformation gradient of the 3D -> higher-d mapping with the given Riemannian metric. We demonstrate the applicability of our method, by using it to construct anisotropic Restricted Voronoi Diagram (RVD) and anisotropic meshing, that are otherwise extremely difficult to compute. In SIFHDE^2 -space constructed by our algorithm, difficult 3D anisotropic computations are replaced with simple Euclidean computations, resulting in an isotropic RVD and its dual mesh on this high-d embedding. Results are compared with the state-of-the-art in anisotropic surface and volume meshings using several examples and evaluation metrics.
more »
« less
- Award ID(s):
- 1657364
- PAR ID:
- 10097916
- Date Published:
- Journal Name:
- ACM transactions on graphics
- Volume:
- 37
- Issue:
- 4
- ISSN:
- 0730-0301
- Page Range / eLocation ID:
- 62:1-16
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Chambers, Erin W. (Ed.)We illustrate the computation of a greedy permutation using finite Voronoi diagrams. We describe the neighbor graph, which is a sparse graph data structure that facilitates efficient point location to insert a new Voronoi cell. This data structure is not dependent on a Euclidean metric space. The greedy permutation is computed in O(n log Delta) time for low-dimensional data using this method.more » « less
-
Riemannian submanifold optimization with momentum is computationally challenging because, to ensure that the iterates remain on the submanifold, we often need to solve difficult differential equations. Here, we simplify such difficulties for a class of structured symmetric positive-definite matrices with the affine-invariant metric. We do so by proposing a generalized version of the Riemannian normal coordinates that dynamically orthonormalizes the metric and locally converts the problem into an unconstrained problem in the Euclidean space. We use our approach to simplify existing approaches for structured covariances and develop matrix-inverse-free 2nd-order optimizers for deep learning in low precision settings.more » « less
-
We propose a method to analyze the three-dimensional nonholonomic system known as the Brockett integrator and to derive the (energy) optimal trajectories between two given points. For systems with nonholonomic constraint, it is well-known that the energy optimal trajectories corresponds to sub-Riemannian geodesics under a proper sub-Riemannian metric. Our method uses symmetry reduction and an analysis of the quotient space associated with the action of a (symmetry) group on R^3. By lifting the Riemannian geodesics with respect to an appropriate metric from the quotient space back to the original space R^3, we derive the optimal trajectories of the original problem.more » « less
-
null (Ed.)Key properties of two-dimensional (2D) layered materials are highly strain tunable, arising from bond modulation and associated reconfiguration of the energy bands around the Fermi level. Approaches to locally controlling and patterning strain have included both active and passive elastic deformation via sustained loading and templating with nanostructures. Here, by float-capturing ultrathin flakes of single-crystal 2H-MoS2 on amorphous holey silicon nitride substrates, we find that highly symmetric, high-fidelity strain patterns are formed. The hexagonally arranged holes and surface topography combine to generate highly conformal flake-substrate coverage creating patterns that match optimal centroidal Voronoi tessellation in 2D Euclidean space. Using TEM imaging and diffraction, as well as AFM topographic mapping, we determine that the substrate-driven 3D geometry of the flakes over the holes consists of symmetric, out-of-plane bowl-like deformation of up to 35 nm, with in-plane, isotropic tensile strains of up to 1.8% (measured with both selected-area diffraction and AFM). Atomistic and image simulations accurately predict spontaneous formation of the strain patterns, with van der Waals forces and substrate topography as the input parameters. These results show that predictable patterns and 3D topography can be spontaneously induced in 2D materials captured on bare, holey substrates. The method also enables electron scattering studies of precisely aligned, substrate-free strained regions in transmission mode.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- The DOI is not currently available.
