Abstract
This paper introduces a robust algorithmic framework for reconstructing semi-algebraic sets—geometric shapes defined by polynomial inequalities—using only a finite number of their power moments. By leveraging Stokes' theorem and specialized renormalized moment matrices, the authors demonstrate that if a shape possesses an algebraic boundary of degree $d$, it can be perfectly recovered from moments of order up to $3d$. For convex sets, this requirement is further reduced to order $2d$. The framework extends to algebraic-exponential measures, providing a powerful tool for inverse problems in tomography and shape recognition.
Introduction
A fundamental challenge in fields such as computerized tomography, computer vision, and shape recognition is the inverse problem of geometric reconstruction: how can we accurately recover the shape of an object given only its moments? A "moment" represents a weighted average of a shape's volume, and while an infinite sequence of moments uniquely defines a measure, practical applications are limited to a finite subset of data.
Previous research successfully addressed this problem for specific geometries, such as polyhedra or convex bodies. This paper generalizes these solutions to any bounded open set in Euclidean space with a real algebraic boundary, exploring the concept of "finite determinateness"—the idea that a finite snippet of data can be sufficient for perfect geometric reconstruction.
Methodology
The authors propose a matrix-based approach rooted in classical calculus, specifically utilizing Stokes' Theorem. This theorem relates the integral of a function over a volume to the integral over its boundary, providing the necessary link between internal moments and boundary geometry.
The Renormalized Moment Matrix
The core of the recovery algorithm is the construction of a specialized matrix, $M^d_k(y)$. Unlike standard moment matrices, these entries are "renormalized" to incorporate the dimension and the order of the monomials. The authors demonstrate that the coefficients of the polynomial defining the set's boundary are contained within the kernel (the null space) of this matrix. Consequently, the exact polynomial vanishing on the boundary can be extracted by solving a linear system.
Algebraic-Exponential Densities
The framework is not restricted to uniform shapes. It extends to "algebraic-exponential data," where the measure's density is the exponential of a polynomial ($\exp(p(x))$). This extension is particularly relevant in statistics and physics, where Gaussian-like distributions are frequently encountered.
Handling Singularities
In instances where the coordinate origin lies on the boundary—a singular case that typically complicates the underlying mathematics—the authors provide a robust workaround. By shifting coordinates or modifying the vector fields used in the Stokes' identity, the algorithm maintains its reconstructive power.
Key Insights and Theoretical Results
Finite Determinateness
A primary contribution of this work is the proof of finite determinateness for semi-algebraic sets. For these objects, the "tail" of the moment sequence is redundant; once the first moments (up to $3d$) are known, every subsequent moment is a deterministic function of the preceding ones. If the set is known to be convex, the data requirement drops significantly to moments of order $2d$.
The Smallest Eigenvalue Heuristic
For real-world shapes that are not perfectly algebraic (e.g., shapes with transcendental boundaries), the authors propose a heuristic based on spectral analysis. They found that the eigenvector corresponding to the smallest eigenvalue of the renormalized moment matrix provides an optimal polynomial approximation of the boundary.
Numerical Validation
The algorithm was validated using several synthetic geometric benchmarks:
- The Annulus: A ring-shaped set defined by two circles. The algorithm successfully identified the rank of the moment matrix and recovered the exact coefficients of the boundary polynomial.
- The Simplex: A basic triangular region in 2D, used to test recovery of linear boundaries.
- Non-algebraic Boundaries: To test approximation limits, the authors used a set defined by an exponential curve ($x_2 \leq \exp(-x_1 + 1)$). Using a degree-4 polynomial approximation, the method yielded an eigenvalue of approximately $10^{-12}$, demonstrating high-precision approximation for smooth, non-polynomial boundaries.
Limitations and Future Work
While the mathematical framework is exact, practical implementation faces two primary hurdles. First, the algorithm assumes the degree $d$ of the boundary polynomial is known, which may require iterative searching in real-world scenarios. Second, the method is sensitive to numerical precision; while it performs well in controlled environments, noisy data would necessitate the integration of robust regularization techniques. Future research will focus on detailed error estimates for non-algebraic boundaries and comparisons with complex orthogonal polynomial reconstruction methods.
Summary updated