On linear approximations to boundaries Using gridded data

Research Report SRR96-004

On linear approximations to boundaries Using gridded data

Peter Hall and Marc Raimondo

Abstract: Imagine placing a straight line into a plane, within which is inscribed a square grid. Colour black each grid vertex that lies above the line, and white each vertex below it. Now remove the line, and attempt to reconstruct it from the pattern of vertex colours on an m x m section of the grid. Using results on the order of approximation to irrational numbers by rationals, and assuming that the line does not pass through any vertex, it is shown that the best possible, achievable accuracy with which the line can be approximated equals O(m^-1), multiplied by a slowly varying function of m, if slope is chosen randomly from the set of all irrational numbers; and O(1) if slope is rational. We apply our results to elucidate the optimal and achievable performance of local linear estimators of smooth boundaries, when data are observed with or without noise.

This service is maintained by the Mathematical Sciences Institute (MSI)
Comments to webmaster@maths.anu.edu.au URL: http://wwwmaths.anu.edu.au/