PaperlayerView exact revision on arXiv

Source-linked AI summary

Recovering Lower-Dimensional Semialgebraic Support of a Measure from its Moments

Ruben Karapetyan, Shenyuan Ma, Ales Wodecki, Jakub Marecek

arXiv:2609.33420v1math.STcs.LGmath.OCstat.TH

TL;DR

Recovering compact, lower-dimensional semialgebraic supports from moments alone remains open when measures need not be finitely atomic. This paper combines moment-matrix kernels with relative Christoffel–Darboux thresholding on a sampled algebraic carrier. Theorem 1 reports an exponential growth with dimension in the ratio of ambient-grid to carrier sampling errors at equal budget.

  • Problem

    Existing approaches do not cover recovery from moments alone for compact, semialgebraic supports of positive codimension that need not be finite.

    Source: §1 · pp. 1–2

  • Method

    The method recovers an algebraic carrier from the moment-matrix kernel, then samples it and thresholds the relative Christoffel–Darboux kernel.

    Source: §1 · p. 2, §4.1 · p. 4, §4.3 · p. 5

  • Results

    Theorem 1 shows that, at equal budget, the ratio of ambient-grid to recovered-carrier sampling errors grows exponentially with dimension n; experiments report larger grid Hausdorff error in every case.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The method estimates compact, semialgebraic supports of positive codimension from moments alone and returns a semialgebraic description together with a finite point sample.

    Source: §6 · p. 10

    For the ordinary relative kernel in codimension at least one, no computable thresholds are known that guarantee Hausdorff convergence, so there is no principled degree or threshold choice.

    Source: §6 · p. 11

Abstract

from arXiv · show

Recovering probability measures from their moments has numerous applications, esp. in connection with the method of moments in statistics and optimization. In the setting where measure need not be finitely atomic, but its support is known to be compact and semialgebraic with codimension at least one, the problem is still open. We combine moment-matrix kernel information with the Christoffel--Darboux kernel to provide a discrete approximation of the support. To validate the proposed approach, we test our algorithm on analytically computed moments and pseudo-moments arising from polynomial optimization problems without unique global minimizers. This complements well-known recent work on recovery of measures with algebraic support, where the kernel of a moment matrix can reveal polynomials vanishing on the support, and on recovery of sufficiently regular full-dimensional supports, where estimators constructed by thresholding the Christoffel--Darboux kernel are known to converge asymptotically to the support.

1 Introduction

The paper targets recovery of compact, lower-dimensional semialgebraic supports from moments alone, including settings where only short, inexact pseudo-moments are available. It combines moment-matrix kernels and Christoffel–Darboux thresholding, and reports an exponential sampling-error advantage for the recovered carrier over an ambient grid.

Prior approaches

  • Existing algebraic methods recover vanishing equations but not inequalities, while known CD convergence results assume sufficiently regular, full-dimensional supports.The latter assumption excludes the positive-codimension supports often arising as polynomial-optimization minimizer sets.Source: §1 · pp. 1–2

Problem and gap

  • The target is a finite point set at small Hausdorff distance from a compact semialgebraic support of positive codimension, using moments alone and no samples.The paper states that it is unaware of an existing method for this task from moments alone.Source: §1 · p. 2

Contributions

  • The proposed procedure first recovers the algebraic carrier from the moment-matrix kernel, then samples it and thresholds the relative CD kernel.The kernel handles equations, while CD thresholding handles inequalities; experiments use both exact moments and pseudo-moments.Source: §1 · p. 2
  • Theorem 1 shows that, at equal budget, the ratio of ambient-grid to recovered-carrier sampling errors grows exponentially with dimension n.The paper also reports experiments on exact moments and pseudo-moments, including POP minimizer sets that are a segment and a semicircle where flat extension fails.Source: §1 · p. 2

2 Related work

Prior support-recovery methods rely either on algebraic information from moment matrices or analytic thresholding of Christoffel–Darboux kernels. Their assumptions leave gaps for non-atomic or lower-dimensional supports.

Vanishing ideals from moment matrices

  • Moment-matrix kernels reveal polynomials vanishing on the support, while generator extraction may require separating new relations from polynomial multiples.Border bases, Gröbner-type reductions, and real-radical computations are among the described tools.Source: §2 · p. 2

Finitely atomic measures

  • For finitely atomic measures, flat extension and truncated GNS methods recover atoms exactly, but these methods do not apply when the measure has a non-atomic part.Related approaches include super-resolution; extraction stability under perturbation is also noted.Source: §2 · p. 2

Christoffel–Darboux kernels and support estimation

  • Known CD support-convergence results assume regular-closed, full-dimensional supports, so they do not cover the lower-dimensional setting considered here.Mollified CD kernels are designed for lower-dimensional cases, but their evaluation requires additional inputs not supplied by moments alone.Source: §2 · pp. 2–3

3 Problem setting

The problem concerns estimating a compact, lower-dimensional semialgebraic support from finitely many moments, without samples from the measure. The algorithm returns both a semialgebraic estimate and a finite sample intended to approximate the support.

3.1 Notation

  • The notation uses R^n, polynomials of bounded degree, truncated moment matrices, real zero sets, and Hausdorff distance.The supplied notation passages introduce monomial vectors and identify polynomials with coefficient vectors, though some displayed definitions are incomplete.Source: §3.1 · p. 3

3.2 Problem statement

  • The support lies on a dimension-s carrier Z with s < n, and the measure is absolutely continuous there with density bounded away from zero.The problem assumes known moments through degree 2d and no samples; the support is specified using polynomial equations and inequalities.Source: §3.2 · p. 3
  • The goal is a finite set within a prescribed Hausdorff tolerance of the support; AlgSup returns a semialgebraic estimate and a finite sample.The approach recovers the carrier from the moment-matrix kernel, samples that carrier, evaluates the relative CD kernel, and retains points below a threshold.Source: §3.2 · pp. 3–4

4 Method

The method uses the moment matrix to recover an algebraic carrier, samples that carrier, and applies a relative Christoffel–Darboux threshold to estimate the support. It returns a semialgebraic set and a finite point sample, but its threshold and degree choices are not guaranteed by theory.

4 Method

  • The method uses the moment matrix first to recover the algebraic carrier and again, through its pseudoinverse, to define a relative CD membership test on that carrier.Points on the carrier are generated between these steps; output and parameter choices are treated separately.Source: §4 · p. 4

4.1 Step 1: the algebraic carrier from the kernel of the moment matrix

  • The moment-matrix kernel yields polynomials vanishing on the support, whose real zero set contains its Zariski closure but may include extra carrier components.The kernel does not recover support inequalities, since it depends only on the Zariski closure.Source: §4.1 · pp. 4–5

4.2 Step 2: sampling the algebraic carrier

  • Random slicing produces points uniformly with respect to the carrier's intrinsic volume, so samples lie exactly on the carrier and their resolution depends on the budget N.The method is used because samples from the measure itself are unavailable.Source: §4.2 · p. 5

4.3 Step 3: the relative Christoffel–Darboux kernel on the carrier

  • The relative CD kernel is computed using the moment matrix's Moore–Penrose pseudoinverse and thresholded on the carrier, but no computable thresholds are known to guarantee convergence in this setting.The paper therefore treats the thresholding rule as heuristic; the alternative mollified kernel requires inputs not supplied by the moments.Source: §4.3 · pp. 5–6

4.4 Output and choice of parameters

  • The output is a semialgebraic estimated support and a finite sample from it, but theory supplies neither a threshold formula nor a degree guaranteeing a prescribed Hausdorff tolerance.The threshold is chosen from the distribution of kernel values on the sample, and the experiments report the attained tolerance.Source: §4.4 · p. 6

5 Experiments

Experiments test the method on closed-form moments and exploratory POP pseudo-moments, including minimizer sets with positive dimension. Across the reported comparisons, restricting kernel evaluation to the recovered carrier yields more accurate support estimates than ambient-grid thresholding.

5.1 Setup and baseline

  • The carrier estimator has a smaller Hausdorff error than ambient-grid thresholding in all nine experiments, although the grid uses higher kernel degrees and more samples in every row.Table 1 compares kernel degrees, sample counts, and Hausdorff distance to the true support.Source: Table 1 · p. 7, §5.4 · p. 9

5.2 Cone moments computed in closed form

  • Both connected components of the cone support are recovered separately from 10,600 accepted points, with Hausdorff distance 0.09.The cone’s defining polynomial is found in the moment-matrix kernel; the accepted set uses degree-6 kernel values thresholded at 82.7.Source: §5.2 · p. 7, Figure 1 · p. 8

5.3 Pseudo-moments from polynomial optimization

  • The POP experiments recover a segment and a semicircle subset from pseudo-moments even though flat extension fails and GNS extraction cannot be used.The relaxation’s moment matrix is passed to Algorithm 1 as if generated by a measure supported on the known minimizer set.Source: §5.3 · pp. 7–8, §5.3.1 · p. 8

5.3.1 The polynomial optimization setting

  • The POP tests use known minimizer sets and evaluate whether pseudo-moments alone recover their geometry, without filtering samples using the known objective or constraints.The examples use a line segment and a subset of a circle.Source: §5.3.1 · p. 8, §5.3 · p. 8

5.3.2 A product of segments in 2n dimensions

  • For stricter accuracy, carrier sampling needs about ten times as many points per added intrinsic dimension across the tested range; the grid baseline fails to reach dH < 0.6 in the reported higher-dimensional tests.The grid baseline is allowed degree 3, while the carrier estimator uses degree 1; for 2n ≥ 8, grid memory becomes a limiting factor.Source: §5.3.2 · pp. 8–9, Figure 2 · p. 9

5.4 The effect of restricting to the carrier

  • On the parabola, carrier restriction avoids the grid’s threshold trade-off: low thresholds leave gaps, while higher thresholds admit points far from the support.The figure reports dH = 0.014 for Algorithm 1, versus 0.095 and 0.17 for the two grid thresholds.Source: §5.4 · p. 9, Figure 3 · p. 10
  • The carrier bounds concern an ideal distance-based selection rule, not Algorithm 1’s CD thresholding; the experiments test whether thresholding approaches that ideal.The carrier sample set must meet the stated dispersion condition for the bound to apply.Source: §5.4 · p. 10
  • For fixed grid resolution, the ambient-grid-to-carrier sampling-error ratio grows exponentially with dimension; the stated evaluation counts do not include the cost of solving polynomial systems on the carrier.The grid-resolution lower bound applies whatever selection function is used.Source: §5.4 · pp. 9–10

6 Conclusion and limitations

The method estimates compact, positive-codimension semialgebraic supports from moments by recovering equations with the moment-matrix kernel and inequalities with the relative Christoffel–Darboux kernel. The conclusion reports lower Hausdorff error than ambient-grid thresholding in every experiment, while open questions constrain parameter choice and numerical robustness.

6 Conclusion and limitations

  • Ambient-grid thresholding has larger Hausdorff error in every experiment, despite using a higher degree; the margin is negligible for the segment and large elsewhere.For a model problem, Theorem 1 shows an exponentially growing gap in attainable error with dimension under an ideal carrier-selection rule.Source: §6 · p. 10
  • For pseudo-moments, the moment-matrix kernel is computed numerically with an inspection-chosen singular-value cutoff; a suitable perturbation theory remains needed.Step 1 is exact for true moments.Source: §6 · p. 10
  • No computable thresholds or convergence rates are known for the ordinary relative kernel in codimension at least one, and the results’ sensitivity to the threshold is unstudied.The sampler also assumes a smooth carrier.Source: §6 · p. 11

A From kernel elements to generators

  • In higher degrees, moment-matrix kernels contain polynomial multiples of earlier relations, so their basis vectors need not be new ideal generators.Extracting generators degree by degree removes multiples of lower-degree kernel elements, using methods such as Gröbner bases or border bases.Source: A From kernel elements to generators · p. 13
  • When the first nontrivial relations occur in degree d, an invertible change of basis among k relations preserves their common zero set.The passage states this under suitable assumptions for carriers defined by several polynomials.Source: A From kernel elements to generators · p. 13

B The random-slicing sampler

The sampler draws random affine slices of a smooth algebraic carrier and returns points with a uniform distribution on that carrier. Its weighting uses a Jacobian-based normalizer, and rejection sampling implements the distribution.

B The random-slicing sampler

  • The construction assumes a smooth algebraic manifold of dimension s with positive finite induced volume.The carrier is defined by the equations F=(f1,…,fk).Source: B The random-slicing sampler · p. 13
  • A Jacobian-based normalizing factor weights slice intersections so their expected count under Gaussian affine slices equals vol(Z).The sampler uses the resulting density for (A,b).Source: B The random-slicing sampler · p. 14
  • Rejection sampling accepts proposed Gaussian slices in proportion to their intersection count, then selects an intersection point with a compensating weight to yield a uniform point on Z.Each intersection-count evaluation requires solving a polynomial system.Source: B The random-slicing sampler · p. 14

C Proof of Theorem 1

Theorem 1 compares support recovery through ambient evaluation points with evaluation on a lower-dimensional carrier. Its proof establishes ambient dispersion lower bounds and a substantially smaller sampling budget for carrier points in the model setting.

C Proof of Theorem 1

  • Any ambient estimate restricted to Gm has Hausdorff error at least the grid’s dispersion from S, regardless of degree or threshold.This applies in particular to a CD-kernel sublevel set on the grid.Source: C Proof of Theorem 1 · p. 14
  • If carrier samples cover S within distance ρ, thresholding points within ρ of S gives Hausdorff error at most ρ.The two one-sided Hausdorff distances are each bounded by ρ.Source: C Proof of Theorem 1 · p. 14
  • For Sn, the degree-one moment-matrix kernel recovers the carrier line exactly through the affine relations xi−x1.Its common zero set is the line R1.Source: C Proof of Theorem 1 · p. 14
  • For the model Sn, the grid’s relative error is at least 1/m and tends to zero only if its evaluation budget grows faster than every exponential in n.The carrier sampling bound achieves target δ with N=⌈2A ln(2A/ϵ)⌉, where A=4√n/δ.Source: C Proof of Theorem 1 · p. 14
  • For any N ambient evaluation points, dispersion is order N^-1/n, while N uniform carrier samples have dispersion order N^-1/s up to a logarithmic factor.The arbitrary-design lower bound follows from covering the ambient box with N balls; the carrier bound assumes local volume growth.Source: C Proof of Theorem 1 · pp. 14–15

D The line segment

The line-segment example uses a moment-matrix relation to identify the carrier and compares CD-kernel thresholding on carrier samples with thresholding on an ambient grid. The figures show kernel values and accepted points at the stated thresholds.

D The line segment

  • The segment minimizers satisfy x1=x2 with −0.5≤x1≤0.5, and the degree-one moment-matrix kernel yields the carrier equation x2−x1=0.The example solves the problem at relaxation order 2.Source: D The line segment · p. 15
  • At degree one, κ1 is evaluated on 1.1×10^4 carrier samples and 10^6 grid points, with threshold τ1=3.36.Figure 4 displays grid kernel values and accepted carrier and grid points at that threshold.Source: D The line segment · p. 15, Figure 4 · p. 15
  • Because τ1 already approximates S sufficiently well, kernels κ2 and κ3 are evaluated only on the grid; computing κ3 requires M3(y), so (10) is solved again at relaxation order 3.Source: D The line segment · p. 15

E The semicircle

For the semicircle, thresholding the relative CD kernel on the recovered circle retains the upper half, despite the moment-matrix kernel recovering only the full circle. The carrier estimate has a smaller Hausdorff error than degree-2 ambient-grid thresholding, while degree-4 grid thresholding reaches the carrier estimate’s error.

E The semicircle

  • The degree-2 moment-matrix kernel recovers x1^2 + x2^2 − 1, but cannot distinguish the semicircle from the full circle or recover x2 ≥ 0.The semicircle and full circle have the same vanishing ideal.Source: E The semicircle · p. 16
  • At degree 2, carrier thresholding gives Hausdorff distance 0.05, versus 0.69 for degree-2 grid thresholding; degree-4 grid thresholding gives 0.05.The carrier result uses κ2 on samples from the circle; the degree-4 grid threshold uses τ_grid = 30.Source: E The semicircle · p. 16
  • Thresholding κ2 on the circle rejects its lower half, where the kernel rises by more than an order of magnitude across x2 = 0.Figure 6 shows κ2 values on a 1000 × 1000 grid and the accepted variety points.Source: E The semicircle · p. 16, Figure 6 · p. 16

F The product of a semicircle and a segment

This example considers a four-dimensional set formed as the product of a semicircle and a segment. Its degree-2 moment-matrix kernel supplies two equations used to sample the carrier, where the CD kernels are evaluated.

F The product of a semicircle and a segment

G Experimental details

The experiments use both analytically computed moments and pseudo-moments from polynomial optimization. The examples with closed-form moments specify their measures and recover carriers from moment-matrix kernels, while the optimization examples use pseudo-moments without further processing.

Examples with moments in closed form

  • For five closed-form experiments, the measure is uniform with respect to Hausdorff measure on a subset of a variety, except for the second hyperbola’s specified parametrized measure.That hyperbola measure has density with respect to arc length bounded above and below, as Problem 1 requires.Source: G Experimental details · p. 18
  • Moments through degree 2d_v are computed in closed form, and the carrier is recovered at the smallest degree with a nontrivial kernel.That degree is 2 for the conics, cone, and cylinder.Source: G Experimental details · p. 18

Examples from polynomial optimization

  • For the segment and semicircle optimization problems, degree-2 relaxation pseudo-moments are used directly; neither moment matrix has a flat extension.Consequently, the cited atom-extraction procedure and GNS construction are unavailable for these pseudo-moment matrices.Source: G Experimental details · p. 18
Loading 2609.33420v1…