Fitting algebraic curves to noisy data

✍ Scribed by Sanjeev Arora; Subhash Khot

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 219 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00012-6

✦ Synopsis

We introduce the following problem which is motivated by applications in vision and pattern detection: We are given pairs of datapoints ðx 1 ; y 1 Þ; ðx 2 ; y 2 Þ; y; ðx m ; y m ÞA½À1; 1  ½À1; 1; a noise parameter d40; a degree bound d; and a threshold r40: We desire an algorithm that enlists every degree d polynomial h such that

If d ¼ 0; this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a polyðm; dÞ time algorithm. However, for d40; the problem as stated becomes ill-posed and one needs a careful reformulation (see the Introduction). We prove a few basic results about this (reformulated) problem. We show that the problem has no polynomial-time algorithm (our counterexample works for r ¼ 0:5). This is shown by exhibiting an instance of the problem where the number of solutions is as large as expðd 0:5Àe Þ and every pair of solutions is far from each other in c N norm. On the algorithmic side, we give a rigorous analysis of a brute force algorithm that runs in exponential time. Also, in surprising contrast to our lowerbound, we give a polynomial-time algorithm for learning the polynomials assuming the data is generated using a mixture model in which the mixing weights are ''nondegenerate.''