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, y1,..., yc) | yj = Pj(x)}, where the pj'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.