Approximation with one-bit polynomials in Bernstein form

DOI10.1007/S00365-022-09608-YMaRDI QIDQ6385939arXivFDO

Authors C. Sinan Güntürk, Weilin Li

Publication date 16 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00365-022-09608-Y

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25) Approximation with constraints (41A29)

arXiv classification

cs.ITmath.CAmath.IT

Abstract: We prove various theorems on approximation using polynomials with integer coefficients in the Bernstein basis of any given order. In the extreme, we draw the coefficients from $pm1$ only. A basic case of our results states that for any Lipschitz function $f:[0,1]o[-1,1]$ and for any positive integer $n$, there are signs $sigm{a}_0,dots,sigm{a}_{n}inpm1$ such that ${\displaystyle }$left |f(x) - sum_{k=0}^n sigma_k , �inom{n}{k} x^k (1-x)^{n-k} ight | leq frac{C (1+|f|_{mathrm{Lip}})}{1+sqrt{nx(1-x)}} ~mbox{ for all } x in [0,1].${\displaystyle }$ More generally, we show that higher accuracy is achievable for smoother functions: For any integer $sgeq1$, if $f$ has a Lipschitz $(s-1)$st derivative, then approximation accuracy of order $O(n^{-s/2})$ is achievable with coefficients in $pm1$ provided $|f{|}_{i}nfty<1$, and of order $O(n^{-s})$ with unrestricted integer coefficients, both uniformly on closed subintervals of $(0,1)$ as above. Hence these polynomial approximations are not constrained by the saturation of classical Bernstein polynomials. Our approximations are constructive and can be implemented using feedforward neural networks whose weights are chosen from $pm1$ only.

This page was built for publication: Approximation with one-bit polynomials in Bernstein form

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6385939)