Premium
On the Computational Complexity of Best L 1 ‐approximation
Author(s) -
Oliva Paulo
Publication year - 2002
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200210)48:1+<66::aid-malq66>3.0.co;2-y
Subject(s) - mathematics , computational complexity theory , mathematical economics , algorithm
It is well known that for a given continuous function f : [0, 1] → ℝ and a number n there exists a unique polynomial p n ∈ P n (polynomials of degree ≤ n ) which best L 1 ‐approximates f . We establish the first upper bound on the complexity of the sequence ( p n ) n ∈ ℕ , assuming f is polynomial‐time computable. Our complexity analysis makes essential use of the modulus of uniqueness for L 1 ‐approximation presented in [13].