I remember learning about how d+1 points uniquely fix a polynomial of degree d and that you can use a slick trick of pretending like each point is a "zero" of the unknown polynomial to write the unknown polynomial as a linear combination of the "zero" polynomials. This requires that all the $x_i$'s are unique, but since we're sampling as time goes on, this is not an issue.
Unfortunately, this takes O(d^2) time, while the methods of piecewise constant and piecewise linear both take O(d) (I'm guessing?) time, but I wonder if this method would yield a better reconstruction of the signal, or much more interestingly, a completely wrong, off-base approximation, since the signal could be a polynomial of degree > d—of which there are infinitely many for each d' > d—or the signal could not be a polynomial at all. :0
@jzhanson Great observation. Yes, you can definitely fit higher-order polynomials to a collection of sample points, in the hope that you get a better fit to the original data. Unfortunately this idea gets you only so far due to Runge's phenomenon. Apart from efficiency, that's one of the big reasons people tend to use piecewise low-order interpolants, rather than higher-order interpolants.
I remember learning about how d+1 points uniquely fix a polynomial of degree d and that you can use a slick trick of pretending like each point is a "zero" of the unknown polynomial to write the unknown polynomial as a linear combination of the "zero" polynomials. This requires that all the $x_i$'s are unique, but since we're sampling as time goes on, this is not an issue.
Unfortunately, this takes O(d^2) time, while the methods of piecewise constant and piecewise linear both take O(d) (I'm guessing?) time, but I wonder if this method would yield a better reconstruction of the signal, or much more interestingly, a completely wrong, off-base approximation, since the signal could be a polynomial of degree > d—of which there are infinitely many for each d' > d—or the signal could not be a polynomial at all. :0
EDIT: this is called Lagrange interpolation
@jzhanson Great observation. Yes, you can definitely fit higher-order polynomials to a collection of sample points, in the hope that you get a better fit to the original data. Unfortunately this idea gets you only so far due to Runge's phenomenon. Apart from efficiency, that's one of the big reasons people tend to use piecewise low-order interpolants, rather than higher-order interpolants.