Theory of the skeleton risk
This chapter develops the asymptotic risk of inductive skeleton fitting from its assumptions to the general scalar formula, then derives the closed forms and comparisons used in Optimal skeleton sampling. The results are organized by mathematical dependence; finite verification and reference tables are collected in Exact verification of the skeleton risk.
Tanaka et al. [TSKH20] derived a Gram recursion and evaluated degrees two and three. The results here give the asymptotic risk and optimal allocation for every dimension and degree, as well as the following explicit evaluations. The conditions in each row are part of the result.
Range |
Result |
|---|---|
Every \(M,D\) and active \(m\) |
Theorem 10: finite scalar sum, with no Gram inverse. |
\(D\geq M\) |
Proposition 1: \(a_{M-1}=\binom{D-1}{M-1}\). |
\(m=D-1,D-2,D-3\), where the skeleton exists |
Proposition 2, Proposition 3 and Theorem 11: formulas uniform in \(M,D\). |
\(M=2\) or \(M=3\), every degree |
Theorem 13, Corollary 4 and Theorem 15: all coefficients in closed form. |
\(m=M-2\) and \(D\geq M-1\) |
Theorem 12: one rational sum. |
Fixed \(D\), growing \(M\) |
Theorem 16: dimension polynomials; Corollary 5: the limit of every coefficient. |
Risk comparison |
Curves win at every degree; Proposition 5 classifies all vertex counts for \(D\leq8\); every fixed degree wins for sufficiently large \(M\). |
The proofs are self-contained apart from the cited small-ball inequality. Statements certified by a finite computation are labeled computer-assisted. The final section lists the ranges where further simplification or a complete risk comparison is still open.
Setting
Let the simplex have \(M\geq2\) vertices \([M]=\{1,\dots,M\}\) and degree \(D\geq1\).
Controls and faces. Controls are indexed by \(\alpha \in \mathbb N^M\) with \(|\alpha| = D\). The Bernstein polynomials are \(B_\alpha(t) = \frac{D!}{\alpha!} t^\alpha\), and \(\operatorname{supp}\alpha = \{i : \alpha_i > 0\}\). For a nonempty face \(I \subseteq [M]\), let
be the controls interior to \(I\) and those on its boundary. \(T_I\) has \(\binom{D-1}{|I|-1}\) elements, so it is empty when \(|I| > D\). On the face \(I\), only the polynomials with support in \(I\) are nonzero.
Gram matrices. Let \(U_I\) be the uniform probability measure on the face \(I\), let \(G^I_{\alpha\beta} = \int B_\alpha B_\beta \, dU_I\), and let \(G = G^{[M]}\). The Dirichlet moments
give the entries exactly. Write \((M)_k = M (M+1) \cdots (M+k-1)\) for the rising factorial. The block \(G^I_{T_I T_I}\) is positive definite, because the Bernstein polynomials are linearly independent on the face.
Model and design. Each response is \(x = b(t) + \varepsilon \in \mathbb R^L\) with \(b(t) = \sum_\alpha B_\alpha(t) b_\alpha\). For every face \(I\) with \(1 \leq |I| \leq \min(D, M)\), \(n_I\) rows are drawn independently from \(U_I\). The noise vectors are independent of the rows and of each other, with mean zero and covariance \(\sigma^2 I_L\). Gaussian noise is not needed.
Estimator. Visit the faces in order of increasing size. On each face \(I\), with \(T = T_I\), estimate the interior controls by least squares on the rows of \(I\), holding the boundary controls at their earlier estimates:
This is fit_skeleton_regression() with unit
weights.
Risk and allocation. The risk is
\(R_N = E \int \lVert \hat b(t) - b(t) \rVert^2 \, dU_{[M]}(t)\) with
\(N = \sum_I n_I\). Let \(N^{(m)}\) be the number of rows on faces with
\(m + 1\) vertices. Assume that each such face receives
\(N^{(m)} / \binom{M}{m+1}\) rows, up to one row, and that
\(N^{(m)} / N \to \rho_m > 0\) for every \(m < \min(D, M)\).
sample_skeleton() with method="random"
produces exactly this design.
Propagation matrices. For a face \(I\) with \(T_I \neq \emptyset\), define \(E_I\) with rows indexed by all controls and columns by \(T_I\):
\(E_I[T_I]\) is the identity;
the row of every control whose support does not contain \(I\) is zero;
for the faces \(J \supsetneq I\) with \(T_J \neq \emptyset\), in order of increasing size,
(2)\[E_I[T_J] = -\bigl(G^J_{T_J T_J}\bigr)^{-1} G^J_{T_J B_J} E_I[B_J].\]
The risk coefficients are
The sum is empty, and \(a_m = 0\), when \(m \geq D\).
skeleton_risk_coefficients() evaluates this
definition in floating point.
The asymptotic risk
Theorem 7 (Asymptotic risk)
Under the assumptions above, \(R_N\) is finite for all sufficiently large \(N\), and
The proof needs to control the inverse of an empirical Gram matrix. Two lemmas do this.
Lemma 1 (Small balls of sums)
Let \(X_1, \dots, X_n \geq 0\) be independent copies of \(X\), and suppose \(P(X \leq x) \leq (A x)^a\) for all \(x > 0\) and some \(A, a > 0\). Then for every \(\delta > 0\),
Proof. For \(\lambda > 0\), \(E e^{-\lambda X} = \int_0^\infty \lambda e^{-\lambda x} P(X \leq x)\,dx \leq \Gamma(a+1) (A / \lambda)^a\). Markov’s inequality applied to \(e^{-\lambda \sum X_i}\) gives \(P(\sum X_i \leq n\delta) \leq e^{\lambda n \delta} (E e^{-\lambda X})^n\). Take \(\lambda = 1/\delta\).
Lemma 2 (Inverse moments of empirical Gram matrices)
Let \(F\) be a face and \(\chi = (B_\alpha)_{\alpha \in T}\) for a set \(T\) of \(k\) controls with supports in \(F\), such that \(H = \int \chi \chi^\top dU_F\) is positive definite. Let \(\hat H_n = \frac1n \sum_{r=1}^n \chi(t_r) \chi(t_r)^\top\), where the \(t_r\) are drawn independently from \(U_F\). Then for every \(q > 0\) there is an \(n_0\) such that \(\sup_{n \geq n_0} E \lVert \hat H_n^{-1} \rVert^q < \infty\). In particular, \(\hat H_n\) is almost surely invertible for \(n \geq n_0\).
Proof. Let \(\psi = H^{-1/2} \chi\) and \(Q(u) = \frac1n \sum_r (u^\top \psi(t_r))^2\). Let \(\lambda\) be the minimum of \(Q\) on the unit sphere. Then \(\lVert \hat H_n^{-1} \rVert \leq \lVert H^{-1} \rVert / \lambda\), so it suffices to bound \(E \lambda^{-q}\).
Bound for one direction. For a unit vector \(u\), \(f = u^\top \psi\) is a polynomial of degree at most \(D\) with \(\int f^2 \, dU_F = 1\). The uniform distribution on a convex set is log-concave, so the inequality of Carbery and Wright [CW01] gives \(P(|f(t)| \leq s) \leq C D s^{1/D}\), with an absolute constant \(C\). Hence \(X = f(t)^2\) satisfies Lemma 1 with \(a = 1/(2D)\) and \(A = (CD)^{2D}\), and
All directions at once. Bernstein polynomials take values in \([0, 1]\), so \(|\psi| \leq K = \lVert H^{-1/2} \rVert \sqrt k\) and \(|\sqrt{Q(u)} - \sqrt{Q(v)}| \leq \sqrt{Q(u - v)} \leq K |u - v|\). Take a \((\sqrt\delta / K)\)-net of the unit sphere with at most \((3K/\sqrt\delta)^k\) points; \(\sqrt\delta \leq 1 \leq K\) for \(\delta \leq 1\), because \(\int |\psi|^2 \, dU_F = k\). If \(\lambda \leq \delta\), some unit vector \(u\) has \(Q(u) \leq \delta\), and the net point \(v\) nearest to it has \(\sqrt{Q(v)} \leq 2\sqrt\delta\). A union bound over the net gives
Moment bound. Choose \(\delta_1 \leq 1\) with \(c_1 \delta_1^a \leq 1\) and an integer \(n_0 > (q + k/2)/a\). For \(n \geq n_0\) and \(\delta \leq \delta_1\), \(c_1 \delta^a \leq (\delta / \delta_1)^a \leq 1\), so the right-hand side is at most \((3K)^k \delta_1^{-a n_0} \delta^{a n_0 - k/2}\). Therefore
which is finite and does not depend on \(n\).
Proof. of Theorem 7
Exact errors. On a face \(I\) with \(T = T_I\) and \(B = B_I\), each row is \(x_r = \sum_{\beta \in B} B_\beta(t_r) b_\beta + \sum_{\alpha \in T} B_\alpha(t_r) b_\alpha + \varepsilon_r\). Let \(Z_T\) and \(Z_B\) be the design matrices of the rows of \(I\), and let \(\hat G^I = Z^\top Z / n_I\) denote the corresponding blocks of the empirical Gram matrix. When \(\hat G^I_{TT}\) is invertible, the normal equations give, exactly, the error matrix (one row per control, one column per output)
Starting from the vertices, this gives \(e = \sum_I \hat E_I \eta_I\), where \(\hat E_I\) is defined by (2) with the empirical blocks \(\hat G^J\) in place of \(G^J\). Condition on all rows. Then the \(\eta_I\) are independent across faces with mean zero, and each column of \(\eta_I\) has covariance \(\sigma^2 (Z_T^\top Z_T)^{-1} = \sigma^2 (\hat G^I_{TT})^{-1} / n_I\). Since \(\int \lVert \hat b - b \rVert^2 dU = \operatorname{tr}(e^\top G e)\),
Almost sure limit. \(R_N\) depends only on the distribution of the design and the noise, so we may take the rows of face \(I\) to be the first \(n_I\) terms of one independent sequence per face. Every \(n_I\) grows without bound. By the strong law of large numbers, \(\hat G^J \to G^J\) almost surely for every face \(J\). The blocks \(G^J_{T_J T_J}\) are invertible, so \(\hat E_I \to E_I\). Since \(N / n_I \to \binom{M}{m+1} / \rho_m\), it follows that \(X_N \to \sum_m a_m / \rho_m\) almost surely.
Uniform integrability. The entries of \(\hat G^J\) lie in \([0, 1]\), and \(N / n_I\) is bounded. Unrolling (2) therefore bounds \(X_N\) by a constant times \(\prod_J (1 + \lVert (\hat G^J_{T_J T_J})^{-1} \rVert)^r\), for a fixed \(r\) and the product over the \(F\) faces with interior controls. By Hölder’s inequality and Lemma 2 with \(q = 2rF\), \(\sup_{N \geq N_0} E X_N^2 < \infty\). Hence \(R_N\) is finite for \(N \geq N_0\), the family \(X_N\) is uniformly integrable, and \(E X_N\) converges to the almost sure limit.
The same argument with a single face, the whole simplex, and all controls gives the all-at-once risk.
Corollary 1 (All-at-once fitting)
For ordinary least squares with all controls on \(N\) rows drawn independently from \(U_{[M]}\), \(N R_N \to \sigma^2 L \operatorname{tr}(G^{-1} G) = \sigma^2 L \binom{D+M-1}{D}\), the number of controls.
Theorem 8 (Optimal ratio)
Over fractions \(\rho_m \geq 0\) with \(\sum_m \rho_m = 1\), \(\sum_m a_m / \rho_m\) is minimized by \(\rho_m = \sqrt{a_m} / \sum_k \sqrt{a_k}\), and the minimum is \((\sum_m \sqrt{a_m})^2\). A zero coefficient receives no rows; the corresponding term is defined as \(0/0=0\), while \(a_m/0=+\infty\) for \(a_m>0\).
Proof. An allocation with \(a_m>0\) and \(\rho_m=0\) has infinite risk. For the remaining allocations, apply Cauchy-Schwarz on the indices with positive coefficients: \((\sum_m \sqrt{a_m})^2 = (\sum_m \sqrt{a_m / \rho_m} \sqrt{\rho_m})^2 \leq \sum_m (a_m / \rho_m) \sum_{m:a_m>0} \rho_m \leq \sum_m a_m/\rho_m\). Equality requires zero share on inactive indices and \(\sqrt{a_m/\rho_m}\) proportional to \(\sqrt{\rho_m}\) on the active ones, giving the stated ratio.
How errors propagate
Fix a face \(I\) with \(|I| = m + 1 \leq D\) and a vector \(c \in \mathbb R^{T_I}\). Its error polynomial is \(p_c(t) = \sum_\alpha B_\alpha(t) (E_I c)_\alpha\). For a face \(J\), the bubble functions of \(J\) are the products \(t^{\mathbf 1_J} g\) with \(g\) a polynomial of degree at most \(D - |J|\). These are exactly the span of \(\{B_\alpha : \alpha \in T_J\}\) on \(J\).
Lemma 3 (Characterization)
\(p_c\) is the unique polynomial of degree at most \(D\) such that
its controls in \(T_I\) are \(c\);
its controls whose support does not contain \(I\) vanish;
for every face \(J \supsetneq I\) with \(|J| \leq D\), its restriction to \(J\) is orthogonal in \(L^2(U_J)\) to the bubble functions of \(J\).
Proof. On \(J\), \(p_c = \sum_{\operatorname{supp}\beta \subseteq J} B_\beta (E_I c)_\beta\), and the supports contained in \(J\) are exactly \(T_J \cup B_J\). Hence (2) reads \(\int B_\alpha p_c \, dU_J = 0\) for every \(\alpha \in T_J\). That is condition (iii). Because \(G^J_{T_J T_J}\) is invertible, (iii) determines the controls in \(T_J\) from those in \(B_J\). Induction on \(|J|\) gives uniqueness. Faces with more than \(D\) vertices have no interior controls and impose no condition.
The propagation from \(I\) to every larger face is determined by the propagation to the faces with one more vertex.
Theorem 9 (Reduction to one more vertex)
Fix \(j \notin I\). Let \(e(\beta, n)\) be the control of \(p_c\) on the face \(I \cup \{j\}\) with entries \(\beta\) on \(I\) and \(n\) at \(j\). By symmetry it does not depend on \(j\). Then for every \(\alpha\) whose support contains \(I\),
Equivalently, let \(\phi(x, y) = \sum_{|\beta| + n = D} e(\beta, n) \frac{D!}{\beta!\,n!} x^\beta y^n\) be the error polynomial on \(I \cup \{j\}\) in homogeneous form, and let \(\Phi = \partial_y (y \phi)\). Then, with \(s_l\) independent and uniform on \([0, 1]\),
Proof. The two forms agree. \(\Phi(x, y) = \sum (n+1) e(\beta, n) \frac{D!}{\beta!\,n!} x^\beta y^n\) and \(E_s (\sum_l s_l t_l)^n = \sum_{|r| = n} \frac{n!}{r!} t^r \prod_l \frac{1}{r_l + 1}\), because \(E s^r = 1/(r+1)\). Multiplying these gives the Bernstein coefficients (3).
Conditions (i) and (ii). Let \(p\) be the polynomial defined by (3). If \(n = 0\), then \((E_I c)_\alpha = e(\alpha, 0) = c_\alpha\). If \(\alpha_i = 0\) for some \(i \in I\), then \(e(\alpha|_I, n)\) is a control of \(I \cup \{j\}\) whose support does not contain \(I\), so it vanishes. It remains to check condition (iii) of Lemma 3.
Reducing (iii) to an integral over a cone. Let \(J = I \cup K\) with \(k = |K| \geq 1\) and \(|J| \leq D\), and let \(g\) be a polynomial of degree at most \(D - |J|\). Write \(x = t_I\), \(|x| = \sum_i x_i\), and parametrize \(U_J\) by \(x\) and by \(t_K\) on the slice \(\sum t_K = 1 - |x|\). By (4) with \(w_l = s_l t_l\),
Substitute this into \(\int p\, t^{\mathbf 1_J} g \, dU_J\), exchange the integrals, and write \(t_K = w + v\) with \(v \geq 0\) and \(\sum v = r = 1 - |x| - \sum w\). The integral of \(g(x, w + v)\) over the simplex of such \(v\) is \(r^{k-1}\) times a polynomial in \((x, w, r)\) of degree at most \(D - |J|\). Integrating over \(w\) on the slices \(\sum w = y\) contributes a factor \(y^{k-1}\). The integral is therefore a combination of
Factoring out the radius. Substitute \((x, y) = \tau\,\omega\), where \(\tau \in (0, 1]\) and \(\omega\) lies in the simplex \(S\) with \(m + 2\) vertices, so that \(dx\,dy = \tau^{m+1} d\tau\, d\omega\). Since \(\Phi\) is homogeneous of degree \(D\), each integral factors into a \(\tau\)-integral times
and \(\omega_I^a \omega_y^{b+k-1}\) has degree at most \(D - m - 2\). So (iii) holds for every \(J\) once
The face with one more vertex. Run the same computation for \(J = I \cup \{j\}\), where \(k = 1\). There \(p = \phi\), because \(\int_0^1 \partial_y(y\phi)(x, sy)\, ds = \phi(x, y)\). The inner integral is \(g(x, 1 - |x|)\), an arbitrary polynomial in \(x\) of degree at most \(D - m - 2\). Take \(g = x^a\). Then the whole integral is a positive \(\tau\)-integral times the integral in (5) with \(h = \omega_I^a\). The orthogonality of \(\phi\) on \(I \cup \{j\}\) therefore gives (5) for these \(h\). These monomials span all polynomials of that degree on \(S\), because \(\omega_y = 1 - |\omega_I|\) there.
Scalar evaluation of every coefficient
The propagation theorem leads to one formula for all dimensions, degrees and skeletons. It separates the angular modes on a face from the moments of the remaining coordinates. Closed forms below are specializations of this formula; a finite sum is available even when no shorter evaluation is known.
Lemma 4 (The outside-coordinate kernel)
Define the formal power series
The quotient is interpreted by its formal series, including on the coordinate axes. In particular, \(K_0(h,l)=\mathbf1_{h=l=0}\) and \(K_1(h,l)=\binom{h+l}{h}/((h+1)(l+1))\). For fixed \(h,l\), the coefficient is a polynomial in \(q\) of degree at most \(h+l\), given by the finite expansion
Here \(\binom qj=0\) for \(j>q\). A useful boundary value is \(K_2(h,0)=K_2(0,h)=2H_{h+1}/(h+2)\), with \(H_j=\sum_{i=1}^j1/i\) and \(H_0=0\).
Proof. Integrating \((1-x-y)^{-1}\) formally once in each variable gives \(xyF\) and the displayed logarithmic expression. Expand \(F^q=(1+(F-1))^q\); since \(F-1\) has no constant term, only \(j\leq h+l\) can contribute to the coefficient. On an axis, \(F(x,0)=\sum_{h\geq0}x^h/(h+1)\). Squaring and using \(1/((j+1)(h-j+1))=((j+1)^{-1}+(h-j+1)^{-1})/(h+2)\) proves the boundary value.
We use shifted Jacobi polynomials \(P_j^{(\alpha,\beta)}(2v-1)\), orthogonal for \((1-v)^\alpha v^\beta\), with endpoint normalization \(P_j^{(\alpha,\beta)}(1)=\binom{j+\alpha}{j}\).
Theorem 10 (Scalar risk sum)
Let \(1\leq s\leq\min(D,M)\), \(n=D-s\), and \(q=M-s\). Use the kernel of Lemma 4. Put
Then
All factorial arguments are nonnegative. Each coefficient extraction uses only terms of degree at most \(n\) in each variable, so every operation is finite, also when \(q=0\) or \(s=1\).
Proof. Angular modes. On the face with \(s\geq2\) vertices, choose an orthogonal basis \(Q_{k,\nu}\) of polynomials of exact orthogonal degree \(k\) for the weight \(\prod_i z_i^2\) under \(U_I\). Here exact orthogonal degree means orthogonal to all polynomials of degree less than \(k\); its dimension is \(d_s(k)=\binom{k+s-2}{s-2}\). The face bubbles \(f_{k,\nu}(z)=\prod_i z_i Q_{k,\nu}(z)\) for \(0\leq k\leq n\) are an orthogonal basis of all face bubbles of degree at most \(D\). For \(s=1\), use only \(Q_{0,1}=1\) and \(f_{0,1}=1\) on the one-point face.
Extension by one vertex. Write \(x=rz\), \(r=\sum_i x_i\) and let \(y\) be the new coordinate. The homogeneous polynomial \(\Phi\) for the boundary mode \(f_{k,\nu}\) is
Indeed the sum, restricted to \(r+y=1\), is \(P_{n-k}^{(0,\,3s+2k-1)}(2r-1)\). To verify (5), divide \(\Phi\) by \(\prod_i x_i\). The weighted volume element is \(r^{3s-1}\prod_i z_i^2\,dr\,dz\). Expand a test polynomial of degree at most \(n-1\) into homogeneous angular modes. Angular orthogonality leaves only its degree \(k\) components. Their remaining radial degrees are at most \(n-k-1\), with weight \(r^{3s+2k-1}\). Jacobi orthogonality makes these integrals zero. At \(y=0\) the radial sum is \(r^{n-k}\), giving the required boundary mode. This proves the extension by the characterization and reduction theorems. At \(n=0\) there are no test polynomials.
The remaining coordinates. By (4), replace each \(y^h\) by
where the \(u_j\) are independent uniform variables on \([0,1]\). If \(q\geq1\), write \(t_{I^c}=(1-r)v\), with \(v\) uniform on its \(q\)-vertex simplex. The Dirichlet moments give
The aggregation \(t_I=rz\) has independent \(z\sim U_I\) and \(r\sim\operatorname{Beta}(s,q)\). Thus the ratio of the squared full-simplex norm of the extended mode to its face norm is
Specifically, the radial beta integral has exponents \(2D+s-h-l-1\) and \(q+h+l-1\); its factor \((q+h+l-1)!\) cancels the corresponding denominator in the preceding moment. The angular norm cancels as well. Trace is invariant under a change of bubble basis, so summing these norm ratios, with \(d_s(k)\) modes, gives the trace for one face. Multiply by \(\binom Ms^2\) for the equal faces and the allocation convention.
When \(q=0\) there is no extension. Only \(h=l=0\) survives in the stated formula, each norm ratio equals one, and the sum is \(\sum_k d_s(k)=\binom{D-1}{s-1}\), including \(s=1\).
Closed forms near the degree
Proposition 1 (Top face)
For \(D \geq M\), \(a_{M-1} = \binom{D-1}{M-1}\).
Proof. For \(I = [M]\), \(E_I\) embeds \(T_I\) and \(G^I = G\), so the trace is \(\operatorname{tr}(G_{TT}^{-1} G_{TT}) = |T_I|\).
Proposition 2 (Faces with D vertices)
For \(D \leq M\),
In particular, \(a_0 = 2M/(M+1)\) for \(D = 1\).
Proof. For \(|I| = D\), \(T_I = \{\mathbf 1_I\}\). No larger face has interior controls, so \(E_I\) is a unit vector and the trace is \(G_{\mathbf 1_I \mathbf 1_I} / G^I_{\mathbf 1_I \mathbf 1_I}\). By (1) this equals \(\frac{(M-1)!}{(2D+M-1)!} \cdot \frac{(3D-1)!}{(D-1)!}\). Multiply by \(\binom{M}{D}\) for the faces and by \(\binom{M}{D}\) from the definition.
Proposition 3 (Faces with D - 1 vertices)
For \(2 \leq D \leq M + 1\),
Proof. Put \(s=D-1\), \(n=1\) and \(q=M-s\) in Theorem 10. The angular degrees \(k=0,1\) have multiplicities \(1,s-1\); the radial vectors are \((1,-3s)\) and \((1)\). With \(K_q(0,0)=1\), \(K_q(1,0)=q/2\) and \(K_q(1,1)=q(q+1)/4\), substitution gives
Replacing \(s=D-1\) and \(q=M-D+1\) gives the stated quadratic. At \(q=0\) it reduces to \(s\), agreeing with Proposition 1, including \(s=1\).
Theorem 11 (Faces with D - 2 vertices)
Let \(D\geq3\), \(s=D-2\), and \(q=M-s\geq0\). Then
where the following quartic applies to every such \(D,M\):
In particular, this includes the full range \(D\geq4\) requested for \(a_{D-3}\), and also \(a_0\) at \(D=3\).
Proof. Apply Theorem 10 with \(n=2\). The angular degrees \(k=0,1,2\) have multiplicities \(1,s-1,s(s-1)/2\). At \(s=1\) only the first is present. The radial coefficient vectors \((A_{k,h})_h\) are
The needed kernel coefficients, obtained by multiplying the constant, linear and quadratic terms of \(F^q\), are
Use symmetry for the reversed arguments. Substitution into the scalar sum gives the displayed quartic after factoring out \((3s-1)!s^2(3s+1)/(64(s-1)!)\). This is a symbolic evaluation with arbitrary \(s,q\), rather than an interpolation in the degree. At \(q=0\) the expression is \(s(s+1)/2=\binom{D-1}{M-1}\), as required by Proposition 1.
Faces of codimension one
Theorem 12 (Faces of codimension one)
For \(s\geq1\), \(M=s+1\), and \(D\geq s\), put \(n=D-s\) and use \(d_s(k)\) from Theorem 10. Then
Thus the two radial sums and the kernel extraction reduce to a single sum of \(n+1\) rational terms; there are no polynomial integrals, Gram matrices or propagation coefficients to compute.
Proof. In the mode extension of Theorem 10, there is just one outside coordinate \(y\). Averaging \(y^h\) multiplies its coefficient by \(1/(h+1)\). Write \(L=n-k\) and \(\beta=3s+2k-1\). The homogeneous radial polynomial therefore becomes, on \(r+y=1\),
The beta density of \(r\) is \(sr^{s-1}\). After the angular norm cancels, the full-to-face squared-norm ratio of this mode is
For completeness, the last integral follows from the reproducing kernel for polynomials of degree at most \(L\) with weight \(r^\beta\). The shifted polynomials \(P_j^{(0,\beta)}\) have squared norms \(1/(2j+\beta+1)\) and endpoint value one. Hence its kernel at endpoint one is \(C_L(r)=\sum_{j=0}^L(2j+\beta+1)P_j^{(0,\beta)}(2r-1)\), with \(\int r^\beta C_L(r)g(r)\,dr=g(1)\). Taking \(g=(1-r)h\), \(\deg h<L\), identifies \(C_L=(L+\beta+1)P_L^{(1,\beta)}\) by orthogonality and \(C_L(1)=(L+1)(L+\beta+1)\). Taking \(g=C_L\) proves \(\int r^\beta P_L^{(1,\beta)}(2r-1)^2\,dr =(L+1)/(L+\beta+1)\). Sum the mode ratios with their multiplicities and multiply by \(\binom{s+1}s^2=(s+1)^2\).
Curves
Theorem 13 (Curves)
For \(M = 2\), \(a_0 = \dfrac{4}{D(D+2)}\) and \(a_1 = D - 1\). A unit error at a vertex has the error polynomial \(\varphi(x) = \sum_k b_k \binom Dk x^k (1-x)^{D-k}\) along the edge, where \(x\) is the coordinate of that vertex and
with \(\tilde P_n(x) = P_n(2x - 1)\) the shifted Legendre polynomials.
Proof. The orthogonal complement of the bubbles. The bubble functions of the edge are \(x(1-x) g\) with \(\deg g \leq D - 2\). For \(n \geq D\), integration by parts gives \(\int_0^1 \tilde P_n'\, x(1-x) g \, dx = -\int_0^1 \tilde P_n \bigl(x(1-x) g\bigr)' dx = 0\). Both boundary terms vanish, and \((x(1-x)g)'\) has degree at most \(D - 1\). The polynomials \(\tilde P_D'\) and \(\tilde P_{D+1}'\) have degrees \(D - 1\) and \(D\). They are independent and span the orthogonal complement of the bubbles in the polynomials of degree at most \(D\), which has dimension two.
The coefficients of φ. \(\tilde P_n'(1) = n(n+1)\) and \(\tilde P_n'(0) = (-1)^{n-1} n(n+1)\). So \(\varphi(1) = 1\) and \(\varphi(0) = 0\) give the stated combination.
The norm of φ. \(\tilde P_D'\) and \(\tilde P_{D+1}'\) are orthogonal, because they have opposite parity about \(x = 1/2\). Integration by parts gives \(\int_{-1}^1 P_n'^2 = P_n(1)P_n'(1) - P_n(-1)P_n'(-1) = n(n+1)\), so \(\lVert \tilde P_n' \rVert^2 = 2n(n+1)\). Therefore \(\lVert \varphi \rVert^2 = \frac14 \bigl(\frac{2}{D(D+1)} + \frac{2}{(D+1)(D+2)}\bigr) = \frac{1}{D(D+2)}\).
The coefficients a_0 and a_1. A vertex block of the Gram matrix is one, so \(a_0 = \binom21 \cdot 2 \lVert \varphi \rVert^2\): the binomial comes from the definition of \(a_m\), and the sum runs over the two vertices. \(a_1 = D - 1\) by Proposition 1.
The Bernstein coefficients. Rodrigues’ formula and the Leibniz rule give \(\tilde P_n = \sum_k (-1)^{n-k} \binom nk \cdot \binom nk x^k (1-x)^{n-k}\), so the Bernstein coefficients of \(\tilde P_n\) are \((-1)^{n-k}\binom nk\). Differentiating, raising the degree of \(\tilde P_D'\) to \(D\), and adding gives \(b_k\).
Corollary 2 (Inductive fitting beats all-at-once fitting on curves)
For \(M = 2\) and every degree, the optimal inductive risk \((\sum_m \sqrt{a_m})^2 = \bigl(\sqrt{D-1} + 2/\sqrt{D(D+2)}\bigr)^2\) is smaller than the all-at-once risk \(D + 1\).
Proof. Expanding, the inequality is \(2\sqrt{(D-1)D(D+2)} < D^2 + 2D - 2\). Both sides are nonnegative. Squaring gives \(0 < (D^2 - 2)^2\), which holds for every integer \(D\).
Theorem 9 with \(m = 0\) turns the curve coefficients into the propagation from a vertex in any dimension.
Corollary 3 (Propagation from a vertex)
For a unit error at vertex \(i\) and every control \(\alpha\) with \(\alpha_i \geq 1\),
At the control \(\mathbf 1_J\) of a face \(J \ni i\) with \(D\) vertices, the error is \(\gamma_D = (-1)^{D-1} (D+1) / 2^D\).
Proof. On the edge, \(e(k, D - k) = b_k\). For \(\mathbf 1_J\), \(\alpha_i = 1\) and \(D b_1 = (-1)^{D-1} (D+1)/2\).
Vertex coefficients in arbitrary dimension
This specialization gives the vertex coefficient and its dimension polynomial directly from the curve controls. It is useful for exact evaluation at fixed \(M\) or \(D\).
Theorem 14 (Vertex specialization and dimension polynomial)
Put \(w_k=(D-k+1)b_k\), with \(b_k\) as in Theorem 13, and use \(F,K_q\) from Lemma 4. For every \(D\geq1\) and \(M\geq2\),
In particular, the polynomial \(P_{D,0}\) in Theorem 16 has the general finite expression
Proof. Fix vertex 1 and write \(\alpha=(k,u)\) and \(\beta=(l,v)\). By Corollary 3, their propagated errors are \(w_k/\prod_j(u_j+1)\) and \(w_l/\prod_j(v_j+1)\). The full Gram entry is
Summing over \(|u|=D-k\) and \(|v|=D-l\) gives exactly \(K_{M-1}(D-k,D-l)\). The vertex Gram block is 1. The \(M\) equal vertex contributions and the allocation factor \(\binom M1=M\) give the factor \(M^2\) in (9).
For the dimension polynomial, expand \(F^{M-1}=(1+(F-1))^{M-1}\). Since \(F-1\) has no constant term, its power \(s\) cannot contribute above \(s=p+q\). Here \(p+q\leq2D-2\), which proves (10), including the degree bound. The coefficient extraction uses a polynomial of bounded degree for every fixed \(D\); it requires no propagation matrices or inverses.
Triangles: all degrees
For \(M=3\), the following formulas determine every coefficient and therefore the optimal risk for every degree. Edge and interior coefficients are zero when the degree is too small to contain their controls.
Corollary 4 (Triangle edge risk in harmonic numbers)
For every \(D\geq2\),
At \(D=1\) there are no edge controls and \(a_1=0\).
Proof. Take \(s=2\), so every \(d_2(k)=1\), and set \(j=D-1-k\) in Theorem 12. Its sum is \(18\sum_{j=1}^{D-1}1/(j(2D+3-j))\). Partial fractions give \(1/(j(C-j))=(1/j+1/(C-j))/C\) with \(C=2D+3\). The two sums are \(H_{D-1}\) and \(H_{2D+2}-H_{D+3}\), respectively.
Theorem 15 (Triangle vertex risk in harmonic numbers)
For every integer \(D\geq1\),
Here \(H_j=\sum_{i=1}^j1/i\), as above. All denominators are positive throughout the stated range. In particular, the formula gives \(3/2,3/8,41/280,79/1120,1189/30800\) at \(D=1,\ldots,5\). It uses a bounded number of harmonic numbers and rational operations, with no kernel coefficient extraction or propagation solve.
Proof. Replace a squared norm by a mixed product. Write \(p_D(x,y,z)\) for the error from a unit error at the vertex \(x=1\), and \(\varphi_D(x)\) for the curve error in Theorem 13. On both incident edges their traces agree, and both vanish on \(x=0\). Therefore \(p_D-\varphi_D(x)\) is a triangle bubble of degree at most \(D\). The propagation characterization gives
For \(D=1,2\) the difference is zero, so this identity still holds. Put \(A_h=(-1)^h\binom{D-1}{h}\binom{D+1}{h}\). The scalar-mode extension with \(s=1\) gives \(p_D=\sum_{h=0}^{D-1}A_h x^{D-h}T_h(y,z)\). Averaging over \((y,z)=(1-x)(v,1-v)\) yields
Only one curve moment is needed. Let \(I_h=\int_0^1(1-x)\varphi_D(x)x^{D-h}(1-x)^h\,dx\). Curve orthogonality implies \(I_h=(-1)^h I_0\): the difference \(x^{D-h-1}(1-x)^h-(-1)^h x^{D-1}\) has degree at most \(D-2\) and is tested against the bubble weight \(x(1-x)\). Also \(\varphi_D(x)=xP_{D-1}^{(1,2)}(2x-1)/D\). Rodrigues’ formula followed by \(D-1\) integrations by parts gives
Every boundary term vanishes because the differentiated Rodrigues factor is \(x^{D+1}(1-x)^D\). The formula includes \(D=1\), where there is no integration by parts. The triangle has uniform density two in \((x,y)\), and the allocation and vertex count give \(a_0=9\int p_D^2\,dU\). Consequently, writing
gives the single sum
Here we used \(\binom{D-1}{h}/((h+1)(h+2)) =\binom{D+1}{h+2}/(D(D+1))\).
Evaluate the weighted harmonic sum. Differentiate the finite Vandermonde identity
at \(u=0\). The generalized binomials here are finite products, so differentiating is elementary and gives
To subtract \(\sum_h w_h/(h+2)\), put
With \(w_D=0\), direct cancellation proves the telescoping identity
One can check it by using \(w_{h+1}/w_h=(D-1-h)(D+1-h)/((h+1)(h+3))\). The boundary values are \(w_DR_D=0\) and \(w_0R_0=-1/((D+2)(D+3))\), so
Subtract this equality from the differentiated Vandermonde identity and substitute in (13). Simplifying, with \(W/\binom{2D}{D}=2D(2D+1)/((D+2)(D+3))\), gives the result. This proves the formula for all \(D\geq1\), including all boundary terms, without a computer-algebra dependency or an inferred recurrence.
Together with Corollary 4 and Proposition 1, this closes every triangle coefficient at every degree: \(a_2(3,D)=\binom{D-1}{2}\) for \(D\geq3\), and \(a_2=0\) otherwise. The optimal risk follows by substituting these three coefficients in Theorem 8. In particular,
Explicit triangular propagation modes
The general extension also gives the following control-level formula, used by the independent exact verification of the triangle risks.
Proposition 4 (Propagation from an edge via Jacobi polynomials)
Let \(m=1\), \(D\geq2\), \(N=D-2\), and let \(I=\{1,2\}\). On the triangle with coordinates \((x_1,x_2,y)\), put \(r=x_1+x_2\) and \(z=x_1/r\). Write the boundary error polynomial as
The polynomial \(\Phi\) of Theorem 9, on this triangle, is
The expression has a polynomial extension to \(r=0\). Homogenize it to degree \(D\) before using (4). More explicitly, the homogeneous polynomial is obtained by replacing the angular factor by
and the radial factor by
Thus \(\Phi=x_1x_2\sum_k d_k H_k R_{N,k}\) in homogeneous coordinates. If its coefficient of \(x_1^a x_2^b y^n\) is \(A_{abn}\), the Bernstein control of the triangle error \(\phi\) is
Proof. Specialize (8) to \(s=2\) and use \(Q_k(z)=P_k^{(2,2)}(2z-1)\). Then \(n=N\), each angular multiplicity is one, and the radial parameter is \(2k+5\). The displayed homogeneous sums are the binomial expansions of those two Jacobi factors. Finally \(\partial_y(y\phi)=\Phi\) divides the coefficient of \(y^n\) by \(n+1\); conversion from monomials to Bernstein controls gives (16).
Fixed degree, growing dimension
Theorem 16 (Rational dependence on the dimension)
For fixed \(D\) and \(m < D\), there is a polynomial \(P_{D,m}\) of degree at most \(2(D - m - 1)\) such that, for every \(M \geq m + 1\),
Proof. Set \(s=m+1\) and \(n=D-s\) in (7). After multiplying by \((M)_{2D}/\binom Ms^2\), all factors except \(K_{M-s}(h,l)\) are independent of \(M\). By (6), this kernel is a polynomial of degree at most \(h+l\leq2(n-k)\leq2n\). Summing gives the claim, including the boundary \(M=s\).
The polynomials through degree eight and their independent orbit-counting verification are in Exact verification of the skeleton risk. They provide exact reference values and the finite calculations needed for the comparison below; they are not substitutes for the all-degree formulas above.
Corollary 5 (Large dimension)
Fix \(D\geq1\) and \(1\leq s\leq D\), and put \(n=D-s\). Every active coefficient has the positive limit
Thus the degree bound in Theorem 16 is attained for every coefficient. For example, \(\lim_{M\to\infty}a_0=2D^2(D+1)^2/4^D\). The optimal inductive risk \((\sum_m\sqrt{a_m})^2\) is bounded in \(M\), while the all-at-once risk \(\binom{D+M-1}{D}\) grows without bound. Inductive fitting therefore wins in all sufficiently high dimensions for every degree.
Proof. Since \(F-1=(x+y)/2+O((|x|+|y|)^2)\), the coefficient of \(q^{h+l}\) in \(K_q(h,l)\) is \(1/(2^{h+l}h!l!)\). In (7), the only term of degree \(2n\) in \(q=M-s\) has \(k=0\) and \(h=l=n\). Its factors are \(d_s(0)=1\), \(A_{0,n}=(-1)^n\binom{n+3s-1}{n}\) and \((2D+s-2n-1)!=(3s-1)!\). Finally \(\binom Ms^2/(M)_{2D}\sim M^{-2n}/(s!)^2\). Substitution gives the stated limit, including \(n=0\) and \(s=1\). Its positivity proves that the polynomial degree is exactly \(2n\). There are only \(D\) active skeletons, so their optimal risk remains bounded as \(M\) grows.
Proposition 5 (Where inductive fitting wins)
The optimal inductive risk is smaller than the all-at-once risk exactly for
\(D = 1\) and \(D = 2\): every \(M \geq 2\);
\(D = 3\): \(M = 2\) and \(M \geq 11\);
\(D = 4\): \(M = 2\) and \(M \geq 20\);
\(D = 5\): \(M \in \{2, 3\}\) and \(M \geq 29\);
\(D = 6\): \(M \in \{2, 3\}\) and \(M \geq 39\);
\(D = 7\): \(M \in \{2, 3\}\) and \(M \geq 49\);
\(D = 8\): \(M \in \{2, 3, 4\}\) and \(M \geq 60\).
The cases \(D \geq 3\) are computer-assisted.
Proof. D = 1. \(a_0 = 2M/(M+1) < 2 \leq M\).
D = 2. By Proposition 3 and Proposition 2, \(a_0 = \frac{3M(3M^2 - 15M + 28)}{2(M+1)(M+2)(M+3)} < \frac92\) and \(a_1 = \frac{30 M (M-1)^2}{(M+1)(M+2)(M+3)} < 30\). Clearing denominators shows both inequalities. So \((\sqrt{a_0} + \sqrt{a_1})^2 < 58 < \binom{M+1}{2}\) for \(M \geq 11\). The cases \(M \leq 10\) are checked directly.
D ≥ 3. \(\binom{M}{m+1}^2 \leq M^{2m+2} / (m+1)!^2\) and \((M)_{2D} \geq M^{2D}\). With the degree bound, this gives \(a_m \leq \sum_i |p_i| / (m+1)!^2\) for all \(M \geq 1\), where \(p_i\) are the coefficients of \(P_{D,m}\). The all-at-once risk exceeds the resulting bound on \((\sum_m \sqrt{a_m})^2\) for \(M \geq 55, 111, 190, 295, 429, 593\) for \(D = 3, 4, 5, 6, 7, 8\), respectively. For every smaller \(M\), evaluating the reference polynomials in floating point with a bound on the rounding error gives the stated sets; the closest comparison differs by a relative \(4.5 \cdot 10^{-3}\). Converting each exact coefficient to float, taking square roots, summing, and squaring has relative error at most \(4(D+1)u\), where \(u = 2^{-53}\). Every comparison lies beyond this error bound.
These results sharpen the observation of Tanaka et al. [TSKH20] that inductive skeleton fitting wins for degrees below three. That observation is a theorem for every \(M\), and the comparison at higher degrees turns around once the dimension is large enough.
Open questions
The asymptotic risk, optimal allocation and a finite scalar expression for every coefficient are proved above. The questions below concern further evaluation of those expressions and the comparison with all-at-once fitting. The curves, all triangle coefficients, the top face, and the families \(m=D-1,D-2,D-3\) are already resolved in closed form.
Shorter evaluations of the remaining nonvertex coefficients. The remaining range is \(M\geq4\), \(D\geq5\) and \(1\leq m\leq\min(D-4,M-2)\). Theorem 10 evaluates every such coefficient by a finite sum. When \(m=M-2\), Theorem 12 already reduces it to a single rational sum. A uniform evaluation without sums whose lengths grow with \(D\), for example in rational functions, harmonic numbers or standard hypergeometric functions, remains to be obtained in this range.
Finite-dimensional vertex coefficients beyond triangles. For \(M\geq4\) and \(D\geq4\), simplify Theorem 14 uniformly in the degree, or give an explicit fixed-order recurrence in \(D\), including its coefficients, initial values and exceptional indices. The triangle formula in Theorem 15 and the fixed-degree dimension polynomials do not supply that general evaluation.
The full comparison at degrees above eight. Proposition 5 classifies every \(M\) at \(D\leq8\). For \(D\geq9\), determine the exact set of winning vertex counts, including any small-dimensional exceptions, and the growth of the eventual crossover as \(D\to\infty\). Corollary 5 proves eventual winning for each fixed degree; it gives no exact crossover law. Closed formulas for a fixed dimension also require a separate inequality analysis before they yield a classification over all degrees.