Paper Info
Title
Robust Fourier and Polynomial Curve Fitting
Abstract
We consider the robust curve fitting problem, for both algebraic and Fourier (trigonometric) polynomials, in the presence of outliers. In particular, we study the model of Arora and Khot (STOC 2002), who were motivated by applications in computer vision. In their model, the input data consists of ordered pairs (x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> ) ε [-1, 1] × [-1, 1], i = 1, 2,..., N, and there is an unknown degree-d polynomial p such that for all but ρ fraction of the i, we have |p(x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> ) - y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> |≤ δ. Unlike Arora-Khot, we also study the trigonometric setting, where the input is from T × [-1, 1], where T is the unit circle. In both scenarios, the i corresponding to errors are chosen randomly, and for such i the errors in the yi can be arbitrary. The goal is to output a degree-d polynomial q such that ||p - q|| <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> is small (for example, O(δ)). Arora and Khot could achieve a polynomial-time algorithm only for ρ = 0. Daltrophe et al. observed that a simple median-based algorithm can correct errors if the desired accuracy δ is large enough. (Larger δ makes the output guarantee easier to achieve, which seems to typically outweigh the weaker input promise.) We dramatically expand the range of parameters for which recovery of q is possible in polynomial time. Specifically, we show that there are polynomial-time algorithms in both settings that recover q up to l∞ error O(δ.99) provided 1) ρ ≤/c1log d and δ ≥ 1/(log d)c, or 2) ρ ≤ c1/log log d/log2 d and δ ≥ 1/dc. Here c is any constant and c1 is a small enough constant depending on c. The number of points that suffices is N = Õ(d) in the trigonometric setting for random x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> or arbitrary x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> that are roughly equally spaced, or in the algebraic setting when the x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> are chosen according to the Chebyshev distribution, and N = Õ(d2) in the algebraic setting with random (or roughly equally spaced) x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> .
Year
DOI
Venue
2016
10.1109/FOCS.2016.75
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
Field
DocType
Error-correction,polynomial regression,Reed-Solomon codes
Log-log plot,Discrete mathematics,Combinatorics,Algebraic number,Polynomial,Curve fitting,Polynomial regression,Unit circle,Fourier transform,Time complexity,Mathematics
Conference
ISSN
ISBN
Citations 
0272-5428
978-1-5090-3934-0
2
PageRank 
References 
Authors
0.39
6
2
Name
Order
Citations
PageRank
V. Guruswami13205247.96
David Zucherman22588266.65