Fitting algebraic curves to noisy data

Sanjeev Arora, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Number of pages8
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002


OtherProceedings of the 34th Annual ACM Symposium on Theory of Computing
CityMontreal, Que.

ASJC Scopus subject areas

  • Software


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

Cite this