arXiv preprint ·
Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study how many bits are needed to write down an elementary analytic expression that uniformly approximates a Lipschitz function. Expressions are finite trees over the basis $\{+,-,\times,÷,\exp\}$ with the variables and rational constants, and their size is $\dc(f)$, the length of the shortest description of $f$ in a fixed binary description language. For functions of one variable we prove that every $L$-Lipschitz $F:[0,1]\to[0,1]$ has an everywhere-defined approximant of accuracy $Δ$ with $\dc(f)\le C\,(L/Δ+\lg(1/Δ+2))$ for all $L,Δ>0$, by a linear spline smoothed with logistic ramps in a description language with one repetition construct. We prove a matching lower bound valid for \emph{every} description language: for $Δ\le 1/36$ and every $L>0$ some $L$-Lipschitz function needs at least $\tfrac1{16}(L/Δ+\lg(1/Δ+2))$ bits. Hence the worst-case description complexity is $Θ(L/Δ+\lg(1/Δ+2))$. For functions on $[0,1]^d$ the same method gives $Θ_d\bigl((L/Δ)^d+\lg(1/Δ+2)\bigr)$, using a tensor-product spline whose coefficients are mixed second differences and cost $O(d)$ bits each. Without the repetition construct the upper bounds carry an additional logarithmic factor, whose necessity for plain expression trees is left open. A reference encoder, decoder and evaluator confirm the constructions numerically, and figures and tables report the checks.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Classical Analysis & ODEs
On the gradient conjecture at infinity: Finite spherical length for gradient trajectories of definable potentials
A Computationally-Efficient Closed-Form $C^{s,1}$-Extension Formula
Resolving Tusnády's Problem
The double descent and Runge phenomena in overparametrized polynomial interpolation
Why Directly Learning Periodic Trajectories Can Fail
Get the few papers worth your time in Classical Analysis & ODEs every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.