More Like this

1. How can classical multidimensional scaling go wrong?

   Sonthalia, Rishi; Van Buskirk, Greg; Raichel, Benjamin; Gilbert, Anna (January 2021, Advances in neural information processing systems)

   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
2. Simplifying Momentum-based Positive-definite Submanifold Optimization with Applications to Deep Learning

   Lin, Wu; Duruisseaux, Valentin; Leok, Melvin; Nielsen, Frank; Khan, Mohammad Emtiyaz; Schmidt, Mark. (June 2023, Proceedings of Machine Learning Research)

   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
3. A Sparse Delaunay Filtration

   Sheehy, Donald R. (July 2021, Leibniz international proceedings in informatics)

   Buchin, Kevin and (Ed.)

   We show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed. 

   more » « less
4. A different look at the optimal control of the Brockett integrator

   https://doi.org/10.1080/00207179.2021.1986232  

   D'Alessandro, Domenico; Zhu, Zhifei (October 2021, International Journal of Control)

   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
5. Greedy Permutations and Finite Voronoi Diagrams

   Chubet, Oliver A.; Macnichol, Paul; Parikh, Parth; Sheehy, Donald R.; Sheth, Siddharth S. (January 2023, 39th International Symposium on Computational Geometry (SoCG 2023))

   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