Real Root Isolation in the Right Basis: Measure-Matched Moment Matrices for High-Degree and Lattice Systems

Many practical problems in robotics, vision and discrete optimization need only the real solutions of a polynomial system, and often only the handful that sit on an integer grid. One family of methods finds these solutions directly. It searches for a "moment matrix", a table of averages of products of monomials taken under an unknown distribution on the real solutions, and requires that table to be positive semidefinite. That requirement filters out complex solutions automatically. The polynomials in the matrix's null space then describe exactly the real solutions. Two papers develop this approach: Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals and Moment matrices, border bases and real radical computation.

The method has a practical weak point: it is written in plain monomials $1, x, x^2, \dots$. At high degree these become nearly indistinguishable on a bounded interval, so the matrix becomes ill-conditioned, the semidefinite solver stalls, and the null space can no longer be read off. The same failure appears when a grid of $K$ integer points is encoded by a degree-$K$ polynomial. This note proposes to write the whole computation in polynomials that are orthogonal for the measure the real roots are expected to live on. That means Chebyshev polynomials on a continuous box, and discrete orthogonal polynomials when the roots lie on a lattice. The null space would then be extracted with a scale-invariant normalization borrowed from approximate vanishing ideals. The claim is that this preserves the algebra exactly while pushing the usable degree well past where monomial methods fail.

Core Claim

The ill-conditioning of moment-based real root isolation is mostly a mismatch between the polynomial basis and the measure on the region where roots are sought. It is not intrinsic to the problem. Four observations support this.

First, any basis whose $k$-th element has the same leading monomial structure as $x^k$ is related to monomials by a triangular matrix $B$. Chebyshev polynomials and discrete orthogonal polynomials both qualify. Writing $M$ for the monomial moment matrix, the moment matrix in the new basis is

$$\tilde M = B^\top M B.$$

Because $B$ is invertible, positive semidefiniteness, rank and null space correspond one-to-one. The order-ideal structure that border bases rely on also carries over, since leading terms are unchanged. Every exactness theorem in the two real-radical papers above therefore transfers. Only the floating-point behaviour changes.

Second, if the basis is orthonormal for a reference measure $\nu$, then $\tilde M$ equals the identity when the unknown measure is $\nu$. The conditioning of $\tilde M$ then measures how far the solution measure is from $\nu$, not how close monomials are to collinear.

Third, when the real roots are known to lie on an integer grid, continuous Chebyshev polynomials are themselves mismatched. The right reference is the uniform measure on the grid points, and the matching basis is the discrete orthogonal (Gram) polynomials. This is where the continuous–discrete mismatch direction enters. It tells us which reference measure to match, and it warns that smooth surrogates for lattice structure behave badly. Such failures are documented in An error term in the Central Limit Theorem for sums of discrete random variables and, for generative models, in CountsDiff. Those papers concern probability approximations, not solvers. We use them only as motivation that the lattice case deserves its own basis, and we test that hypothesis rather than assume it.

Fourth, the final step, choosing the rank of a nearly singular matrix, is itself a discrete decision made from a continuous spectrum. We replace the raw eigenvalue threshold with a coefficient-normalized generalized eigenvalue problem (defined below). The design follows Spurious Vanishing Problem in Approximate Vanishing Ideal. That paper showed that, without normalization, polynomials look like they vanish merely because their coefficients are tiny: coefficient norms swung from $10^{-15}$ to $10^{10}$ in unnormalized Vanishing Component Analysis, a method for learning polynomials that vanish on point clouds.

The closest existing work is the border-basis moment method. It shrinks the semidefinite matrix from the full count of monomials up to the degree, $\binom{n+d}{d}$, down to roughly the number of solutions. On Katsura-4 the matrix size drops from 56 to 16, and on Bifur from 165 to 16. The authors still name numerical instability and the need for 128-bit arithmetic as unresolved. Our proposal keeps their indexing and changes the basis and the extraction rule. Sharper Bounds for Chebyshev Moment Matching supplies evidence that Chebyshev moments resist noise far better than monomial moments. It does so for density recovery, not root isolation. We reuse the idea and not the analysis.

Research Program

The first component is a border-basis moment solver parameterized by the basis. The user, or a cheap bounding step, supplies a box or a grid. Variables are affinely mapped to $[-1,1]$. For each coordinate the solver builds either a Chebyshev basis or a Gram polynomial basis orthonormal on the grid points. Multivariate elements are tensor products indexed by the same order ideal the border-basis method would use.

Multiplication matrices and the linear constraints imposed by the input equations are expressed directly in this basis using three-term recurrences. Monomials are never expanded, so the triangular matrix $B$ is never formed numerically. Grid constraints are a special case. The defining polynomial $\prod_k (x-k)$ has enormous monomial coefficients, but in the Gram basis it is simply the next polynomial in the sequence, a single vector.

The second component is the extraction rule. Instead of thresholding eigenvalues of the solver output $\tilde M$, we solve

$$\min_{c}\ \frac{c^\top \tilde M c}{\|c\|^2_{W}},$$

where $c$ is a coefficient vector in the chosen basis and $W$ is the norm induced by the reference measure. The rank is set at the largest ratio gap between consecutive generalized eigenvalues. This criterion does not change if a candidate polynomial is multiplied by a constant. A raw eigenvalue threshold does change, and that is how spurious vanishing enters.

The third component is an analysis. For a zero-dimensional system whose real roots are well separated in the reference metric, we aim to bound the condition number of the optimal $\tilde M$ in terms of the minimum root weight and the separation. Monomial bounds instead grow exponentially in degree. This is the place where a negative result could appear. If no such bound holds for clustered roots, we will characterize the regime in which the method does not help.

Baselines

The naive reference point is complex-then-filter. Solve the system over the complex numbers with a mature solver, discard roots whose imaginary part exceeds a tolerance, and for lattice problems round the survivors to the nearest grid point. We run it on identical systems with matched wall-clock budgets and the same tolerance-tuning budget as our method. The solvers are a Gröbner-basis eigenvalue method and homotopy continuation as packaged in standard software. No reported result was found on Lacuna for complex-then-filter accuracy on these suites. Beating it means recovering the correct real root set on systems where it either times out or produces wrong real-root counts. Those failures come from the cascading rounding errors documented for elimination solvers in Two Minimal Problems for Cameras with Radial Distortion and Solution Space Analysis of Essential Matrix Based on Algebraic Error Minimization.

The strongest existing method is the border-basis moment method of Moment matrices, border bases and real radical computation in monomials, run in double and in 128-bit precision. It is the strongest competitor because it already solves the matrix-size problem; any gain we show must therefore come from conditioning, not size. Its reported numbers are matrix sizes: 16 versus 56 for graded moments on Katsura-4, and 16 versus 165 on Bifur. No reported result was found on Lacuna for its root accuracy or convergence rate at high degree. We will therefore reimplement it and run it on the same semidefinite solver, tolerances and order ideals as our method.

Beating it means two things. In double precision we should recover correct real roots at degrees where the monomial version fails, with the same matrix sizes. We should also match its 128-bit accuracy at double-precision cost.

The full graded moment hierarchy of Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals is a secondary reference. For grid problems we also include Lasserre's grid relaxation from Polynomials nonnegative on a grid and discrete optimization. On 10-variable MAX-CUT with uniform off-diagonal weights it reports reaching the optimum at the second relaxation, a semidefinite program with 385 variables.

Three ablations isolate the key ingredients. The first keeps monomials but adds diagonal (Jacobi) rescaling and the affine map to $[-1,1]$. The second uses the orthogonal basis with plain eigenvalue thresholding. The third uses Chebyshev on lattice problems in place of Gram polynomials. Each separates one ingredient: basis versus mere scaling, basis versus extraction rule, and continuous versus discrete reference measure.

Why not just…?

Why not just use 128-bit arithmetic? This is a real threat on small systems, and the border-basis authors themselves point to it. Precision buys a fixed number of extra digits, while monomial conditioning worsens exponentially with degree. So extended precision should only shift the failure degree by a constant. Semidefinite solvers in extended precision are also much slower. Our degree sweep reports the failure degree for monomial double, monomial 128-bit and orthogonal double. If 128-bit monomials track our method's failure degree at acceptable cost, the conditioning claim is wrong for practical sizes and we will report that.

Why not just rescale variables and normalize the matrix diagonal? This is the cheapest preconditioner and the most dangerous alternative. Diagonal scaling fixes differences in magnitude but cannot undo near-collinearity between $x^{k}$ and $x^{k+2}$ on $[-1,1]$. The orthogonal change of basis removes that collinearity. The first ablation tests this directly. If it closes most of the gap, the contribution narrows to the extraction rule and the lattice basis, and we will reframe the paper accordingly rather than overclaim.

Why not just solve over the complex numbers, keep real roots, and round to the grid? When complex solutions vastly outnumber real ones, this wastes work, and elimination templates lose or invent roots through accumulated rounding. Both points are made in the papers cited above. Still, for small or well-conditioned systems it may simply win on time. We expect it to remain competitive there and say so. The decisive question is accuracy and failure rate as degree and grid size grow. We test that question on the same instances.

Why not just encode the grid with Lasserre's exact grid polynomials? That is what we do; the difference is the basis. Lasserre's exactness result is the theoretical justification for the lattice regime. Its own discussion, and the Moment-SOS survey (The Moment-SOS hierarchy: Applications and related topics), acknowledge that high-degree grid polynomials make solvers fail in floating point. Comparing Gram and monomial encodings of identical grid constraints settles whether the basis is the fix.

Proposed Experiments

The algebraic suites are Katsura-4 and Katsura-5, Bifur, cyclic roots and the robot kinematic systems used in the border-basis paper. For these we report matrix size, which should match the reported 16 on Katsura-4 and Bifur, together with real-root count correctness, maximum root error, solver termination status and the condition number of $\tilde M$.

We then build degree-scaled families. One extends Katsura-type systems to higher $n$. Another is a synthetic family of zero-dimensional systems with planted real roots plus many complex roots, with total degree swept upward. The headline metric is the largest degree at which each method still returns the correct real roots in double precision.

The lattice regime uses systems whose real solutions are planted on $\{0,\dots,K\}^n$ with grid constraints of degree $K+1$. We sweep $K$ from 4 to 64. We also include random MAX-CUT instances, checking that we reproduce the reported second-order behaviour at 10 variables before scaling up. A stress variant perturbs the input coefficients by small continuous noise. It compares our lattice-constrained extraction with solve-then-round, measuring the fraction of exactly recovered integer roots as noise grows relative to grid spacing.

Two checks are decisive. The first is whether orthogonal-basis double precision beats Jacobi-scaled monomials, and not just raw monomials, in failure degree on the synthetic sweep. The second is whether Gram polynomials beat Chebyshev on the lattice sweep. A yes on the first supports the core claim. A yes on the second supports the specific role of the discrete reference measure. A no on the second means a single continuous basis suffices, which would simplify the method and is worth knowing.