Abstract: We propose a functional view of matrix decomposition problems on graphs such
as geometric matrix completion and graph regularized dimensionality reduction.
Our unifying framework is based on the key idea that using a reduced basis to
represent functions on the product space is sufficient to recover a low rank
matrix approximation even from a sparse signal. We validate our framework on
several real and synthetic benchmarks (for both problems) where it either
outperforms state of the art or achieves competitive results at a fraction of
the computational effort of prior work.