Conclusions

I presented two multiscale methods for sparse data interpolation problems: multiscale regularization and the quadtree pyramid. Multiscale regularization produced an order-of-magnitude speedup (100 iterations versus 1000) in convergence for least squares interpolation of sparsely sampled topographical data, compared to regularization with a simple Laplacian. The quadtree pyramid produces a result which is of decent quality, with essentially no cost - roughly one iteration. When used as a starting guess for iterative solutions (simple Laplacian regularization), the quadtree pyramid result leads to a good result for ten times fewer iterations.