Matrix Decomposition on Graphs: A Functional View

We propose a functional view of matrix decomposition problems on graphs such as geometricmatrix completion and graph regularized dimensionality reduction. Our unifyingframework is based on a key idea that using reduced basis to represent a function on theproduct space of graph is sufficient to recover a low rank matrix approximation even froma sparse signal. We validate our framework on several real and synthetic benchmarks (forboth problems) where it either outperforms state of the art or achieves competitive resultsat a fraction of the computational effort of prior work.