A Computationally-Efficient Closed-Form Cs,1-Extension Formula
Abstract
We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order s of a Cs,1 function f:ℝd→ℝ at N distinct points in [0,1]d. The reconstruction satisfies bounds on its global Cs,1 seminorm and its Lipschitz constant on [0,1]d that are independent of the sample size N, the latter being the sharp Whitney condition. For s≥2, the reconstruction is real analytic away from the data points and definable in the o-minimal structure ℝexp. Our nonlinear extension formula coincides with the formula of McShane (1934) for s=0 and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for s=1, and is new for s≥2. For fixed d and s≥2, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with 𝒪(N) gates and 𝒪(log N) depth. This yields 𝒪(N) storage and 𝒪(log N) parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with 𝒪(N) one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the 𝒪(Nlog N) initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.
Related
- No closed-form formula for Stiefel geodesics
- A closed signature formula for the Katz-Long-Moody Hermitian form
- A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations
- Computationally Efficient Experimental Design with Generalized Posteriors
- Computationally efficient interval estimation for the 1-1-1 multilevel mediation analysis model in R: A replication of Bauer, Preacher, and Gil (2006)
BibTeX
@misc{kratsios2026computationallyefficient,
title = {{A Computationally-Efficient Closed-Form $C^s,1$-Extension Formula}},
author = {Anastasis Kratsios and Philipp Zimmermann},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12239},
eprint = {2610.12239},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12239},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Computationally-Efficient Closed-Form C^s,1-Extension Formula
AU - Anastasis Kratsios
AU - Philipp Zimmermann
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12239
UR - https://arxiv.org/abs/2610.12239
AB - We identify explicit closed-form and variational formulae for interpolating the exact values and derivatives through order s of a C^s,1 function f:ℝ^d→ℝ at N distinct points in [0,1]^d. The reconstruction satisfies bounds on its global C^s,1 seminorm and its Lipschitz constant on [0,1]^d that are independent of the sample size N, the latter being the sharp Whitney condition. For s≥2, the reconstruction is real analytic away from the data points and definable in the o-minimal structure ℝ_exp. Our nonlinear extension formula coincides with the formula of McShane (1934) for s=0 and with the formulae of Le Gruyer and Phan (2015) and Azagra, Le Gruyer, and Mudarra (2018) for s=1, and is new for s≥2. For fixed d and s≥2, our closed-form formula is computable away from the data points by a circuit using only elementary unary and binary real operations, with 𝒪(N) gates and 𝒪(log N) depth. This yields 𝒪(N) storage and 𝒪(log N) parallel evaluation time. From the supplied coefficients and weights, the circuit can be compiled with 𝒪(N) one-time work in the exact-real word-RAM model. Thus, in this supplied-data setting, our nonlinear construction improves by a logarithmic factor on the 𝒪(Nlog N) initialization bound of Fefferman and Klartag (2009), while retaining linear storage and attaining logarithmic query time through parallel evaluation.
ER -