The Inverse Moment Problem for Convex Polytopes

Nick Gravin, Jean B. Lasserre, Dmitrii V. Pasechnik, Sinai Robins

Abstract

This paper presents a novel, exact algorithm for reconstructing the vertices of a $d$-dimensional convex polytope from a finite set of its integral moments. By integrating discrete geometry identities with classical signal processing techniques, the authors demonstrate that $N$ vertices can be uniquely recovered using $O(Nd)$ axial moments. Notably, the method remains robust even when the internal density of the polytope is an unknown polynomial, and it avoids the computational pitfalls of traditional "slicing" approximations in higher dimensions.

Introduction

The "inverse moment problem" is a fundamental challenge in fields ranging from computer tomography and gravimetry to signal processing. It asks a deceptively simple question: can the geometry of an object be uniquely determined if we only know its moments (weighted averages of its shape, such as mass, center of gravity, or inertia tensors)?

While this problem is well-understood for two-dimensional shapes, higher-dimensional reconstruction ($d > 2$) has historically relied on approximation techniques or iterative slicing methods that lack geometric precision. This research addresses the challenge of exact reconstruction for $d$-dimensional convex polytopes, providing a rigorous mathematical framework to identify precise vertex coordinates from minimal global measurements.

Methodology

The proposed algorithm bridges the gap between discrete geometry and algebraic signal processing through two primary mathematical pillars:

1. BBaKLP Formulas

Named after Brion, Barvinok, Khovanskii, Lawrence, and Pukhlikov, these identities are powerful tools in polyhedral geometry. They allow an integral over a polytope to be expressed as a sum of terms associated specifically with its vertices. In the context of moments, these formulas transform a global measurement (the integral) into a sum of local data points, effectively mapping the polytope's moments to the coordinates of its vertices.

2. Prony’s Method and Hankel Matrices

To extract the vertex coordinates from the moment data, the authors employ Prony’s method—a classic signal processing technique used to identify the frequencies of a signal composed of a sum of exponentials. The authors prove that the scaled moments of a polytope satisfy a linear recurrence. By organizing these moments into a Hankel matrix, the kernel (null space) of the matrix yields the coefficients of a univariate polynomial. The roots of this polynomial correspond to the projections of the polytope's vertices onto a specific axis.

The Reconstruction Algorithm

The reconstruction process follows a structured pipeline:

  1. Direction Selection: Choose $d+1$ vectors (directions) in general position.
  2. Moment Collection: For each direction, collect a sequence of axial moments.
  3. Matrix Construction: Build a Hankel matrix for each direction and determine its rank to identify the number of vertices $N$.
  4. Root Finding: Solve for the roots of the resulting polynomials to find vertex projections.
  5. Triangulation: Match these projections across the $d+1$ directions to calculate the full $d$-dimensional coordinates for every vertex.

Key Insights

Density Independence

A significant finding of this work is that the exact vertex set can be recovered even if the internal density function $\rho$ of the polytope is unknown, provided $\rho$ is a polynomial. The algorithm effectively "skips" the unknown density by increasing the number of required moments relative to the degree of the density polynomial.

Automatic Vertex Counting

Unlike many reconstruction algorithms that require the number of vertices ($N$) as an input parameter, this method determines $N$ automatically. The rank of the Hankel matrix serves as a direct indicator of the number of distinct vertices, making the approach more flexible for black-box applications.

Linear Complexity

While high-dimensional problems often suffer from the "curse of dimensionality," the authors prove that $N$ vertices in $\mathbb{R}^d$ are uniquely determined by $O(Nd)$ moments. This linear relationship between the data requirements and the number of vertices/dimensions represents a significant improvement in efficiency over previous methods.

Results and Complexity

The research establishes that the algorithm is exact; in the absence of measurement noise, it retrieves the precise vertex set of the polytope. For rational polytopes—those where vertices have rational coordinates—the problem is solvable in polynomial time using the LLL (Lenstra–Lenstra–Lovász) algorithm for root finding. This theoretical efficiency suggests that the method is not only mathematically sound but computationally viable for complex geometric structures.

Limitations and Future Directions

Despite its theoretical strengths, the method faces practical hurdles. Prony-like methods are notoriously sensitive to noise; in real-world scenarios where sensor data is imperfect, the reconstruction may require stabilization techniques such as Singular Value Decomposition (SVD) or Total Least Squares.

Furthermore, the current framework is strictly limited to convex polytopes. Non-convex shapes or objects with internal voids would require a different geometric approach to account for the more complex relationship between moments and vertices. Finally, while this paper focuses on shape recovery, the authors suggest that once the vertices are known, the same framework could be reversed to solve for the unknown density function $\rho$, opening new avenues for material science and non-destructive testing.

Summary updated

BibTeX
@article{gravin2012inverse,
  author = {Nick Gravin and Jean B. Lasserre and Dmitrii V. Pasechnik and Sinai Robins},
  title = {{The Inverse Moment Problem for Convex Polytopes}},
  journal = {Discret. Comput. Geom.},
  year = {2012},
  doi = {10.1007/s00454-012-9426-4},
}
Figure