Fitting algebraic curves to noisy data

Sanjeev Arora, Subhash Khot

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


Motivated by applications in vision and pattern detection, we introduce the following problem. We are given pairs of datapoints (x1, y1), (x2, y2),...,(xm, ym), a noise parameter δ > 0, a degree bound d, and a threshold ρ > 0. We desire "every" degree d polynomial h satisfying h(xi) ∈ [yi - δ, yi + δ] for at least ρ fraction of i's. We assume by rescaling the data that each xi, yi ∈ [-1, 1]. If δ = 0, this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a poly(d, 1/ρ) time algorithm. We show a few basic results about the problem. We show that there is no polynomial time algorithm for this problem as defined; the number of solutions can be as large as exp(dρ.5-e) even if the data is generated using a 50-50 mixture of two polynomials. We give a rigorous analysis of a brute force algorithm for the version of this problem where the data is generated from a mixture of polynomials. Finally, in surprising contrast to our "lower bound", we describe a polynomial-time algorithm for reconstructing mixtures of O(1) polynomials when the mixing weights are "nondegeneration." The tools used include classical theory of approximations.

Original languageEnglish (US)
Pages (from-to)162-169
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Fitting algebraic curves to noisy data'. Together they form a unique fingerprint.

Cite this