  This paper develops a framework for fitting functions with domains in the
Euclidean space, when data are sparse but a slow variation allows for a useful
fit. We measure the variation by Lipschitz Bound (LB). Functions which admit
smaller LB are considered to vary more slowly. Since most functions in practice
are wiggly and do not admit a small LB, we extend this framework by
approximating a wiggly function, f, by ones which admit a smaller LB and do not
deviate from f by more than a specified Bound Deviation (BD). In fact for any
positive LB, one can find such a BD, thus defining a trade-off function (LB-BD
function) between the variation measure (LB) and the deviation measure (BD). We
show that the LB-BD function satisfies nice properties: it is non-increasing
and convex. We also present a method to obtain it using convex optimization.
For a function with given LB and BD, we find the optimal fit and present
deterministic bounds for the prediction error of various methods. Given the
LB-BD function, we discuss picking an appropriate LB-BD pair for fitting and
calculating the prediction errors. The developed methods can naturally
accommodate an extra assumption of periodicity to obtain better prediction
errors. Finally we present the application of this framework to air pollution
data with sparse observations over time.
