Topological Grammars for Data Approximation

Abstract

A method of {\it topological grammars} is proposed for multidimensional data approximation. For data with complex topology we define a {\it principal cubic complex} of low dimension and given complexity that gives the best approximation for the dataset. This complex is a generalization of linear and non-linear principal manifolds and includes them as particular cases. The problem of optimal principal complex construction is transformed into a series of minimization problems for quadratic functionals. These quadratic functionals have a physically transparent interpretation in terms of elastic energy. For the energy computation, the whole complex is represented as a system of nodes and springs. Topologically, the principal complex is a product of one-dimensional continuums (represented by graphs), and the grammars describe how these continuums transform during the process of optimal complex construction. This factorization of the whole process onto one-dimensional transformations using minimization of quadratic energy functionals allow us to construct efficient algorithms.

Corrected Journal version, Appl. Math. Lett., in press. 7 pgs., 2 figs

References in corpus (1)

• Elastic principal manifolds and their practical applications

Cited by in corpus (14)

• Principal Graphs and Manifolds
• Principal manifolds and graphs in practice: from molecular biology to dynamical systems
• Robust And Scalable Learning Of Complex Dataset Topologies Via Elpigraph
• Scikit-dimension: a Python package for intrinsic dimension estimation
• Trajectories, bifurcations and pseudotime in large clinical datasets: applications to myocardial infarction and diabetes data
• Fractional norms and quasinorms do not help to overcome the curse of dimensionality
• Quasi-Equilibrium Closure Hierarchies for The Boltzmann Equation
• Order--disorder separation: Geometric revision
• Data complexity measured by principal graphs
• Domain Adaptation Principal Component Analysis: base linear method for learning with out-of-distribution data
• Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning
• Geometrical complexity of data approximators
• PCA Beyond The Concept of Manifolds: Principal Trees, Metro Maps, and Elastic Cubic Complexes
• Dealing with complexity of biological systems: from data to models