More Like this

1. Too many secants: a hierarchical approach to secant-based dimensionality reduction on large data sets

   https://doi.org/10.1109/HPEC.2018.8547515  

   Kvinge, Henry; Farnell, Elin; Kirby, Michael; Peterson, Chris (September 2018, 2018 IEEE High Performance extreme Computing Conference (HPEC))

   A fundamental question in many data analysis settings is the problem of discerning the “natural” dimension of a data set. That is, when a data set is drawn from a manifold (possibly with noise), a meaningful aspect of the data is the dimension of that manifold. Various approaches exist for estimating this dimension, such as the method of Secant-Avoidance Projection (SAP). Intuitively, the SAP algorithm seeks to determine a projection which best preserves the lengths of all secants between points in a data set; by applying the algorithm to find the best projections to vector spaces of various dimensions, one may infer the dimension of the manifold of origination. That is, one may learn the dimension at which it is possible to construct a diffeomorphic copy of the data in a lower-dimensional Euclidean space. Using Whitney's embedding theorem, we can relate this information to the natural dimension of the data. A drawback of the SAP algorithm is that a data set with T points has O(T 2 ) secants, making the computation and storage of all secants infeasible for very large data sets. In this paper, we propose a novel algorithm that generalizes the SAP algorithm with an emphasis on addressing this issue. That is, we propose a hierarchical secant-based dimensionality-reduction method, which can be employed for data sets where explicitly calculating all secants is not feasible. 

   more » « less
2. Too many secants: a hierarchical approach to secant-based dimensionality reduction on large data sets

   Henry Kvinge, Elin Farnell (October 2018, 2018 IEEE High Performance Extreme Computing Conference (HPEC ‘18))

   A fundamental question in many data analysis settings is the problem of discerning the ``natural'' dimension of a data set. That is, when a data set is drawn from a manifold (possibly with noise), a meaningful aspect of the data is the dimension of that manifold. Various approaches exist for estimating this dimension, such as the method of Secant-Avoidance Projection (SAP). Intuitively, the SAP algorithm seeks to determine a projection which best preserves the lengths of all secants between points in a data set; by applying the algorithm to find the best projections to vector spaces of various dimensions, one may infer the dimension of the manifold of origination. That is, one may learn the dimension at which it is possible to construct a diffeomorphic copy of the data in a lower-dimensional Euclidean space. Using Whitney's embedding theorem, we can relate this information to the natural dimension of the data. A drawback of the SAP algorithm is that a data set with $$n$$ points has $n(n-1)/2$ secants, making the computation and storage of all secants infeasible for very large data sets. In this paper, we propose a novel algorithm that generalizes the SAP algorithm with an emphasis on addressing this issue. That is, we propose a hierarchical secant-based dimensionality-reduction method, which can be employed for data sets where explicitly calculating all secants is not feasible. 

   more » « less
3. Manifold Coordinates with Physical Meaning

   Samson J. Koelle; Hanyu Zhang; Marina Meila; Yu-Chia Chen (June 2022, Journal of machine learning research)

   Manifold embedding algorithms map high-dimensional data down to coordinates in a much lower-dimensional space. One of the aims of dimension reduction is to find intrinsic coordinates that describe the data manifold. The coordinates returned by the embedding algorithm are abstract, and finding their physical or domain-related meaning is not formalized and often left to domain experts. This paper studies the problem of recovering the meaning of the new low-dimensional representation in an automatic, principled fashion. We propose a method to explain embedding coordinates of a manifold as non-linear compositions of functions from a user-defined dictionary. We show that this problem can be set up as a sparse linear Group Lasso recovery problem, find sufficient recovery conditions, and demonstrate its effectiveness on data 

   more » « less
4. Geometric learning for computational mechanics, Part III: Physics-constrained response surface of geometrically nonlinear shells

   https://doi.org/10.1016/j.cma.2023.116219  

   Xiao, Mian; Ma, Ran; Sun, WaiChing (October 2023, Computer Methods in Applied Mechanics and Engineering)

   De Lorenzis, Laura; Papadrakakis, Manolis; Zohdi, Tarek I. (Ed.)

   This paper presents a graph-manifold iterative algorithm to predict the configurations of geometrically exact shells subjected to external loading. The finite element solutions are first stored in a weighted graph where each graph node stores the nodal displacement and nodal director. This collection of solutions is embedded onto a low-dimensional latent space through a graph isomorphism encoder. This graph embedding step reduces the dimensionality of the nonlinear data and makes it easier for the response surface to be constructed. The decoder, in return, converts an element in the latent space back to a weighted graph that represents a finite element solution. As such, the deformed configuration of the shell can be obtained by decoding the predictions in the latent space without running extra finite element simulations. For engineering applications where the shell is often subjected to concentrated loads or a local portion of the shell structure is of particular interest, we use the solutions stored in a graph to reconstruct a smooth manifold where the balance laws are enforced to control the curvature of the shell. The resultant computer algorithm enjoys both the speed of the nonlinear dimensional reduced solver and the fidelity of the solutions at locations where it matters. 

   more » « less
5. The decomposition of the higher-order homology embedding constructed from the k-Laplacian

   Chen, Yu-Chia; Meila, Marina (December 2021, Advances in neural information processing systems)

   M. Ranzato; A. Beygelzimer; Y. Dauphin; P.S. Liang; J. Wortman Vaughan (Ed.)

   The null space of the k-th order Laplacian Lk, known as the {\em k-th homology vector space}, encodes the non-trivial topology of a manifold or a network. Understanding the structure of the homology embedding can thus disclose geometric or topological information from the data. The study of the null space embedding of the graph Laplacian L0 has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the k-th homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the {\em connected sum} of manifolds as a perturbation to the direct sum of their homology embeddings. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components. The proposed framework is applied to the {\em shortest homologous loop detection} problem, a problem known to be NP-hard in general. Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images. 

   more » « less