TY - JOUR

T1 - Approximation with One-Bit Polynomials in Bernstein Form

AU - Güntürk, C. Sinan

AU - Li, Weilin

N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - 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 { ± 1 } only. A basic case of our results states that for any Lipschitz function f: [0 , 1] → [- 1 , 1] and for any positive integer n, there are signs σ, ⋯ , σn∈ { ± 1 } such that |f(x)-∑k=0nσk(nk)xk(1-x)n-k|≤C(1+|f|Lip)1+nx(1-x)forallx∈[0,1].More generally, we show that higher accuracy is achievable for smoother functions: For any integer s≥ 1 , if f has a Lipschitz (s- 1) st derivative, then approximation accuracy of order O(n-s/2) is achievable with coefficients in { ± 1 } provided ‖ f‖ ∞< 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 { ± 1 } only.

AB - 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 { ± 1 } only. A basic case of our results states that for any Lipschitz function f: [0 , 1] → [- 1 , 1] and for any positive integer n, there are signs σ, ⋯ , σn∈ { ± 1 } such that |f(x)-∑k=0nσk(nk)xk(1-x)n-k|≤C(1+|f|Lip)1+nx(1-x)forallx∈[0,1].More generally, we show that higher accuracy is achievable for smoother functions: For any integer s≥ 1 , if f has a Lipschitz (s- 1) st derivative, then approximation accuracy of order O(n-s/2) is achievable with coefficients in { ± 1 } provided ‖ f‖ ∞< 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 { ± 1 } only.

KW - Bernstein polynomials

KW - Integer constraints

KW - Noise shaping

KW - Sigma-delta quantization

KW - ± 1 Coefficients

UR - http://www.scopus.com/inward/record.url?scp=85144557020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85144557020&partnerID=8YFLogxK

U2 - 10.1007/s00365-022-09608-y

DO - 10.1007/s00365-022-09608-y

M3 - Article

AN - SCOPUS:85144557020

JO - Constructive Approximation

JF - Constructive Approximation

SN - 0176-4276

ER -