How can we capture the global geometry of a dataset or the behavior of a complex polynomial system without evaluating every single point or root individually? The answer often lies in moments. By computing the statistical expectations of monomials over a data distribution, we can construct a moment matrix. This matrix acts as a powerful algebraic lens, encoding shapes, densities, and boundaries.
However, this mathematical elegance comes with a severe computational penalty: as the number of variables or the polynomial degree increases, the size of these matrices explodes combinatorially. Understanding why this scaling happens—and how it impacts applications from anomaly detection to optimization—is central to modern algebraic data analysis.
How Moment Matrices Capture Geometry
To build intuition, imagine a cloud of data points scattered across a multi-dimensional space. Instead of tracking each point explicitly, we can compute its empirical moments—such as the mean, variance, and higher-order polynomial combinations. As shown by Edouard Pauwels et al. in Data Analysis from Empirical Moments and the Christoffel Function, this empirical moment matrix can perfectly identify the underlying dimension and density of the space where the data resides, even if it is restricted to complex algebraic shapes like spheres or tori.
A primary mechanism for extracting this geometry is the Christoffel function, a classical tool from approximation theory. Edouard Pauwels et al. demonstrated in Sorting out typicality with the inverse moment matrix SOS polynomial that a polynomial constructed by inverting the moment matrix acts as an affine-invariant "contour map" of a data cloud. Where the data is dense, the Christoffel function takes distinct values; where data is sparse or non-existent, it spikes, making it an exceptional tool for outlier and anomaly detection. In a comprehensive review, Jean B. Lasserre outlines in The Christoffel function: Applications, connections and extensions how this single algebraic structure bridges the gap between algebraic geometry and probability theory.
The Root of the Combinatorial Explosion
Why does this approach suffer from such a severe computational bottleneck? The issue is fundamental to the nature of multivariate polynomials. If we have $n$ variables and wish to capture features up to a polynomial degree $d$, the number of possible monomials is given by the combinatorial formula:
$$\binom{n+d}{d}$$
A moment matrix indexes these monomials along both its rows and columns. Consequently, the matrix size grows exponentially relative to both the dimensionality of the data and the degree of the polynomials used.
This combinatorial scaling severely restricts the practical deployment of these methods. For instance, Jean B. Lasserre et al. note in Optimal Data Fitting: A Moment Approach that while moment-sum-of-squares (SOS) relaxations can fit complex semi-algebraic shapes to hundreds of thousands of data points, the dimensionality of the feature space itself is typically constrained to under 20 dimensions. Beyond this, the underlying matrices become too massive to store or process using standard semidefinite programming (SDP) solvers, a limitation originally detailed by Jean B. Lasserre in A moment approach to analyze zeros of triangular polynomial sets.
Impact Across Domains
The consequences of this combinatorial scaling ripple across several distinct research areas:
- Data Streams and Classification: For real-time applications, the memory footprint must remain minimal. While the Christoffel function allows for instant updates without storing historical data—as explored by Kévin Ducharlet et al. in Leveraging the Christoffel function for outlier detection in data streams and by Jean B. Lasserre in Leveraging the properties of the Christoffel function for anomaly detection in data streams—the exponential growth in matrix size limits its use to low-dimensional feature spaces. Similarly, Jean B. Lasserre shows in On the Christoffel function and classification in data analysis that moment-based classification faces the same dimensional barriers.
- Density Estimation: When reconstructing probability distributions from limited windows, Constantinos Costis Daskalakis et al. demonstrate in A Statistical Taylor Theorem and Extrapolation of Truncated Densities that high-degree multivariate polynomials incur substantial practical overhead, limiting scalability despite strong theoretical guarantees.
- Polynomial System Solving: The bottleneck is not unique to statistics. In control theory and computer algebra, researchers often translate non-linear polynomial systems into linear algebra frameworks using Macaulay or border matrices. Philippe Dreesen et al. demonstrate in Weighted/Structured Total Least Squares problems and polynomial system solving and Back to the Roots: Polynomial System Solving, Linear Algebra, Systems Theory that while this translation guarantees global root finding, the resulting coefficient matrices grow prohibitively large. This same limitation appears when identifying limit cycles in non-linear systems (Shuqi Zhang et al. in Limit Cycle Identification in Nonlinear Polynomial Systems) and when computing real roots directly via semidefinite programming (Jean B. Lasserre et al. in Moment matrices, border bases and real radical computation).
- Geometric and Topological Representations: Finding approximate vanishing ideals—polynomials that evaluate to near-zero on a dataset—faces an identical barrier. Hiroshi Kera et al. explain in Spurious Vanishing Problem in Approximate Vanishing Ideal that the exponential growth of the monomial search space hinders high-dimensional scaling. This computational overhead also restricts algebraic representations of topological features, such as persistence diagrams (Zhichao Wang et al. in Polynomial Representation for Persistence Diagram).
Mitigating the Curse of Dimensionality
To make moment-based methods viable in higher dimensions, recent research focuses on structural modifications that bypass the full monomial expansion. One prominent direction is regularization and localization.
For example, Jean B. Lasserre introduces a regularized variant in A modified Christoffel function and its asymptotic properties that replaces point-evaluation with local averages over small boxes. This modification allows the recovery of true data densities without needing to map the entire global geometry of the support, offering a pathway toward more scalable, sparsity-promoting polynomial approximations.
Key Foundational Work
A moment approach to analyze zeros of triangular polynomial sets (2005) — contributed 1 concept elements to this direction.
Measures with zeros in the inverse of their moment matrix (2008) — contributed 1 concept elements to this direction.