Fitting algebraic curves to noisy data
Sanjeev Arora, Subhash Khot · 2002
Motivated by applications in vision and pattern detection, we introduce the following problem. We are given pairs of datapoints (x 1 , y 1 ), (x 2 , y 2 ), bound d, and a threshold # > 0. We desire "every" degree d polynomial h satisfying #, y i for at least # fraction of i's.