reconstructing curves in three (and higher) dimensional space from noisy data
We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form C = [(x,y 1 ,,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 .
random errors maximum distance separable codes decoding algorithm algebraic codes error-correction