Bounds on bits needed for approximating smooth functions closely
Description Complexity Bounds for Analytic Approximations of Lipschitz Functions
Computation and Language
Summary
This paper looks at how complicated a math formula needs to be to closely imitate a smooth curve that changes steadily without sudden jumps. They show that for simple functions of one variable, the shortest way to write a formula that keeps the error below a tiny amount depends roughly on how wiggly the curve is and the desired accuracy. They also prove this is the smallest possible length for any way of writing such formulas. For functions with several inputs, the complexity grows quickly as the number of dimensions increases. The authors provide both mathematical proofs and computer checks of their results.
What this means in practice
- •For numerical software developers: Design compact analytic functions to approximate Lipschitz continuous data precisely within controlled error bounds.
- •For signal processing engineers: Estimate minimal formula complexity needed to model smooth signals for efficient encoding and reconstruction.
Tested on simulated data.
Authors
Artem Vozmishchev
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.