McGregor, Andrew ;
Rudra, Atri ;
Uurtamo, Steve
Polynomial Fitting of Data Streams with Applications to Codeword Testing
Abstract
Given a stream of $(x,y)$ points, we consider the problem of finding univariate polynomials that best fit the data. Over finite fields, this problem encompasses the wellstudied problem of decoding ReedSolomon codes while over the reals it corresponds to the wellstudied polynomial regression problem.
We present onepass algorithms for two natural problems: i) find the polynomial of a given degree $k$ that minimizes the error and ii) find the polynomial of smallest degree that interpolates through the points with at most a given error bound. We consider a range of error models including the average error per point, the maximum error, and the number of points that are not fitted exactly. Many of our results apply to both the reals and finite fields. As a consequence we also solve an open question regarding the tolerant testing of codes in the data stream model.
BibTeX  Entry
@InProceedings{mcgregor_et_al:LIPIcs:2011:3032,
author = {Andrew McGregor and Atri Rudra and Steve Uurtamo},
title = {{Polynomial Fitting of Data Streams with Applications to Codeword Testing}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {428439},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3032},
URN = {urn:nbn:de:0030drops30322},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.428},
annote = {Keywords: Streaming, Polynomial Interpolation, Polynomial Regression}
}
2011
Keywords: 

Streaming, Polynomial Interpolation, Polynomial Regression 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Related Scholarly Article: 


Issue date: 

2011 
Date of publication: 

2011 