Sampling Complexity of Hyperbolic-Cross Approximation

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A hyperbolic-cross polynomial space selects multivariate monomials using a product-type degree bound. Sampling complexity is the number of function values needed to achieve the specified approximation error with the prescribed confidence.

Statement recorded in the supplied source.

Can better sampling measures lower the sample complexity of hyperbolic-cross polynomial approximation, and can sample-complexity estimates be proved for domains that are not unions of rectangles with nonvanishing volume, including triangles, simplices, and spheres? [S2]

Scope qualification.

The polynomial index set, function norm, sampling method, and quantitative success criterion must be taken from the source.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Improve sampling distributions and prove sample bounds for hyperbolic-cross approximation on the listed geometries.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003454 (OWR-15222-001). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Multiscale and High-Dimensional Problems $2018$, Oberwolfach Reports, DOI 10.4171/owr/2017/17, pp. 1001--1051 https://doi.org/10.4171/owr/2017/17. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003454 and source code OWR-15222-001 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The polynomial-frame talk in OWR 17/2017, pp. 1007--1009, was read. It approximates on an irregular domain using polynomials orthogonal on an enclosing tensor-product domain, regularizes small singular values, and asks for improved sampling and nonrectangular-domain bounds. The following known leverage-density calculation is rederived in a finite orthonormal space on the physical domain. Its basis and sampling assumptions differ from the source's conveniently available ambient frame; that difference is part of the obstruction, not silently removed.

Research attempt: Leverage sampling on a triangle and the frame-conditioning gap

A finite-space sampling calculation.

Let $\mu$ be a probability measure and let real functions $\phi_1,\ldots,\phi_N$, $N\ge1$, be orthonormal in $L^2(\mu)$. Assume they can be evaluated, and define \[ k(x)=\sum_{j=1}^N\phi_j(x)^2,\qquad \rho(x)=k(x)/N. \] Then $\int\rho\,d\mu=1$. Sample $X$ from $\rho\,d\mu$ and put $v(X)=\phi(X)/\sqrt{\rho(X)}$ where $\rho>0$. The zero-density set has sampling probability zero; all $\phi_j$ vanish there. Therefore \[ \mathbb E[vv^T]=I_N,\qquad \|v\|_2^2=N. \] For $m$ independent samples set $G=m^{-1}\sum_{i=1}^m v_i v_i^T$. Entrywise independence and zero mean of $vv^T-I$ give \[ \mathbb E\|G-I\|_F^2 =\frac1m\mathbb E\|vv^T-I\|_F^2 =\frac{N^2-N}{m}. \] Here $\operatorname{tr}((vv^T)^2)=\|v\|^4=N^2$ and $\mathbb E\operatorname{tr}(vv^T)=N$. Since $\|A\|_2\le\|A\|_F$, Markov's inequality implies \[ \Pr(\|G-I\|_2>\epsilon)\le\frac{N^2-N}{m\epsilon^2}. \] Thus $m\ge(N^2-N)/(\delta\epsilon^2)$ gives the two-sided norm comparison $(1-\epsilon)\|c\|^2\le c^TGc\le(1+\epsilon)\|c\|^2$ with probability at least $1-\delta$, for $0<\epsilon,\delta<1$. For $N=1$, the Gram matrix is identically $1$ for any $m\ge1$. This elementary bound is quadratic, not the near-linear estimate sought in the source.

Among arbitrary sampling densities $\eta$ positive wherever $k>0$, the worst squared row norm is $\operatorname*{ess\,sup}k/\eta$, necessarily at least $N$ because $\int k=N$ and $\int\eta=1$. Equality is attained by $\rho$. Likewise Cauchy--Schwarz gives $\int k^2/\eta\,d\mu\ge(\int k\,d\mu)^2=N^2$. Hence the proposed density minimizes these two particular row statistics. This is not a proof that it minimizes every sample-complexity or regularization criterion.

A nonrectangular example worked explicitly.

Let $\Omega=\{(x,y):x,y\ge0,\ x+y\le1\}$ with uniform probability measure $d\mu=2\,dx\,dy$. Direct integration gives $\mathbb Ex=\mathbb Ey=1/3$, $\mathbb Ex^2=\mathbb Ey^2=1/6$, and $\mathbb Exy=1/12$. An orthonormal basis of the affine polynomials is \[ 1,\qquad \sqrt{18}(x-1/3),\qquad \sqrt{24}(y+x/2-1/2). \] Indeed the last two have mean zero, variances one and covariance zero by the displayed moments. Here \[ k(x,y)=1+18(x-1/3)^2+24(y+x/2-1/2)^2. \] Its minimum is $1$ at the centroid, and its maximum is $9$: it is convex and every triangle point is a convex combination of vertices, where its value is $9$. Thus uniform sampling has worst squared row norm $9$, whereas sampling with density $k/3$ and the corresponding reciprocal-square-root weights makes it exactly $3$. This is a concrete distributional improvement on a triangle, though only for this three-dimensional space and these row statistics.

The failed transfer to the full frame problem.

For an arbitrary hyperbolic-cross restriction one could try to form its physical-domain Gram matrix and whiten it into an orthonormal basis. But that construction requires the very integrals and stable inverse square root not supplied by the enclosing-box model, and small eigenvalues can make the coefficient transform enormous. On a sphere, an ambient polynomial system containing $1,x_1^2,\ldots,x_d^2$ is even exactly dependent under restriction because $\sum x_i^2-1=0$; an inverse square root does not exist until the nullspace is removed. The physical $L^2$ comparison proved above consequently does not establish the original SVD-truncated ambient-coefficient estimates, a practical sampler on every implicit domain, or near-linear hyperbolic-cross complexity.

Verification and adversarial audit

The probability bound was derived by an exact second-moment computation without invoking an unchecked matrix-concentration theorem. The triangle moments were integrated explicitly, the maximum checked at all three vertices, and the zero-density and $N=1$ cases treated. The sphere example tests the whitening hypothesis and demonstrates an actual singularity rather than only possible numerical ill-conditioning.

Audit corrections.

Distinguished an orthonormal basis on the physical domain from the source's ambient polynomial frame. Included the weak quadratic bound actually proved, instead of claiming an unproved near-linear concentration estimate or a free whitening algorithm.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The full original geometry, hyperbolic-cross dimension dependence, practical density construction, regularized frame coefficient control and desired improvement beyond quadratic sample complexity remain unresolved. The calculation is a restricted basis-based route and a worked failure of its automatic transfer to the source's frame model; no general new original-target progress is claimed.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46681 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written-proof review of this attempt; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.