# A Markov Variation Approach to Smooth Graph Signal Interpolation

arXiv: https://arxiv.org/abs/1806.03174 · HTML: https://mlsanity.com/paper/1806.03174/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2018.

## Built on by (most cited first, 2 of 2)

- [Task-Based Graph Signal Compression](https://mlsanity.com/paper/2110.12387/) (2021)
- [Diffusion Maps for Signal Filtering in Graph Learning](https://mlsanity.com/paper/2312.14758/) (2023)

## Abstract (arXiv)

In this paper we present the Markov variation, a smoothness measure which offers a probabilistic interpretation of graph signal smoothness. This measure is then used to develop an optimization framework for graph signal interpolation. Our approach is based on diffusion embedding vectors and the connection between diffusion maps and signal processing on graphs. As diffusion embedding vectors may be expensive to compute for large graphs, we present a computationally efficient method, based on the Nystr"om extension, for interpolation of signals over a graph. We demonstrate our approach on the MNIST dataset and a dataset of daily average temperatures around the US. We show that our method outperforms state of the art graph signal interpolation techniques on both datasets, and that our computationally efficient reconstruction achieves slightly reduced accuracy with a large computational speedup.