I introduce two strategies to overcome the slow convergence of these interpolation problems. Firstly, I implement a composite regularization operator which applies a 2-D Laplacian at different spatial scales. Use of the multiscale operator to regularize the least squares interpolation of a sparsely sampled topographical map produces an order-of-magnitude speedup in convergence, compared to the case of regularizing with the single-scale 2-D Laplacian. Secondly, I implement a quadtree-style scheme to explicitly interpolate sparsely sampled data. The quadtree method is fast, and as shown on the topographical intepolation example, produces reasonable results itself, and may also be used as an initial guess for inversion schemes.