Fast framelet transforms on manifolds

Abstract: 

Data in a practical application with some structure can be viewed as sampled from a manifold, for instance, data on graphs and in astrophysics. An important case is a smooth and compact Riemannian manifold M, such as a sphere, torus, cube or graph. In this work with Xiaosheng Zhuang, we construct a type of tight framelet using quadrature rules on M for the representation of data. The derived framelets can be used for processing the data (e.g., inpainting an image on M).

One critical computation for framelets is to compute, from the framelet coefficients of the input data (which are assumed at the finest level), the framelet coefficients at lower levels, and also to evaluate the function values at new nodes using the framelet representation. We design an efficient computational strategy, called a fast framelet transform (FMT), to compute the framelet coefficients and to recover the function. Assuming the fast Fourier transform (FFT) on the manifold M, the FMT has the same computational complexity as the FFT. Numerical examples illustrate the efficiency and accuracy of the FMT algorithm.