Matrix Decomposition on Graphs: A Functional View

Abhishek Sharma (1) , Maks Ovsjanikov (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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 a key idea that using reduced basis to represent a function on the product space of graph 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.

Domaines: Apprentissage [cs.LG]; Vision par ordinateur et reconnaissance de formes [cs.CV]

Abhishek Sharma, Maks Ovsjanikov. Matrix Decomposition on Graphs: A Functional View. 2020. ⟨hal-02871840v2⟩