Fitting algebraic curves to noisy data

ABSTRACT

(MATH) 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)$, $\ldots,(x_m, y_m)$, a noise parameter $\delta > 0$, a degree bound $d$, and a threshold $\rho>0$. We desire "every" degree $d$ polynomial $h$ satisfying h(x_i) \in [y_i -\delta, y_i +\delta] & \qquad \nonumber for at least &rgr; fraction of i's.(MATH) We assume by rescaling the data that each $x_i, y_i \in [-1, 1]$.(MATH) If $\delta =0$, this is just the list decoding problem that has been popular in complexity theory and for which Sudan gave a $\poly(d,1/\rho)$ 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^{0.5 -&egr;}) 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 "nondegenerate.The tools used include classical theory of approximations.

REFERENCES

• 1: Sigal Ar , Richard J. Lipton , Ronitt Rubinfeld , Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data, SIAM Journal on Computing, v.28 n.2, p.487-510, April 1999 [doi>10.1137/S0097539796297577]
• 2: J Canny, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.6, p.679-698, Nov. 1986 [doi>10.1109/TPAMI.1986.4767851]
• 3: S. Dasgupta, E. Pavlov, and Y. Singer. An efficient PAC algorithm for reconstructing a mixture of lines. Manuscript, Nov 2001.
• 4: R. A. DeVore and G. G. Lorentz. Constructive Approximation. Springer Verlag, Berlin Heidelberg 1993.
• 5: Richard O. Duda , Peter E. Hart, Use of the Hough transformation to detect lines and curves in pictures, Communications of the ACM, v.15 n.1, p.11-15, Jan. 1972 [doi>10.1145/361237.361242]
• 6: T. Erdelyi. Markov-Bernstein type inequalities for polynomials under Erdos-type constraints. Paul Erdos and his (MATH)ematics, July 4-11, 1999, Budapest, Hungary , to appear.
• 7: P. Erdös. On extremal properties of the derivatives of polynomials. Ann. of (MATH)., 2:310--313, 1940.
• 8: M. Grotschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, 1993.
• 9: Manfred H. Hueckel, An Operator Which Locates Edges in Digitized Pictures, Journal of the ACM (JACM), v.18 n.1, p.113-125, Jan. 1971 [doi>10.1145/321623.321635]
• 10: J. Illingworth , J. Kittler, A survey of the Hough transform, Computer Vision, Graphics, and Image Processing, v.44 n.1, p.87-116, Oct. 1988 [doi>10.1016/S0734-189X(88)80033-1]
• 11: V. F. Leavers, Which Hough transform?, CVGIP: Image Understanding, v.58 n.2, p.250-264, Sept. 1993 [doi>10.1006/ciun.1993.1041]
• 12: G. G. Lorentz. Approximation of functions, 2nd Ed., Chelsea, New York, NY, 1986.
• 13: D. Marr. Vision , W.H. Freeman, 1982.
• 14: D. Marr and E. Hildreth. Theory of edge detection. Proc. Royal Soc. of London, 207:187--217, 1980.
• 15: J.S. Mill. An examination of Sir William Hamilton's philosophy, Longman Green, London 1889. Discusses in Selective History of Theories of Visual Perception.
• 16: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
• 17: L.G. Valiant. Deductive learning. Phil. Trans. Royal Soc. Lond., A 312:441--446, 1984.
• 18: L. Welch and E. R. Berlekamp. Error correction of algebraic block codes, US Patent Number 4,633,470, December 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for
      G.1.7 Ordinary Differential Equations
          Subjects: Boundary value problems

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory