Reconstructing curves in three (and higher) dimensional space from noisy data

ABSTRACT

We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y₁,•••,y_c) | y_j = p_j(x)], where the p_j's are polynomials of low degree. Given n points in (c+1)-dimensional space, such that t of these lie on some such unknown curve C while the other n-t are chosen randomly and independently, we give an efficient algorithm to recover the curve C and the identity of the good points. The success of our algorithm depends on the relation between n, t, c and the degree of the curve C, requiring t = Ω (n deg(C)) ^1/(c+1). This generalizes, in the restricted setting of random errors, the work of Sudan (J. Complexity, 1997) and of Guruswami and Sudan (IEEE Trans. Inf. Th. 1999) that considered the case c=1.

REFERENCES

• 1: D. Bleichenbacher, A. Kiayias, and M. Yung. Manuscript, 2002.
• 2: V. Guruswami , P. Indyk, Expander-Based Constructions of Efficiently Decodable Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.658, October 14-17, 2001
• 3: Venkatesan Guruswami , Piotr Indyk, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510023]
• 4: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 5: A. Kiayias and M. Yung. Manuscript, 2002.
• 6: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

General Terms:
Algorithms, Reliability, Theory

Keywords:
algebraic codes, decoding algorithm, error-correction, maximum distance separable codes, random errors