# Construction of Tight Frames on Graphs and Application to Denoising

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2014.

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

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Topologically penalized regression on manifolds](https://mlsanity.com/paper/2110.13749/) (2021)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach](https://mlsanity.com/paper/2203.03036/) (2022)
- [Large Graph Signal Denoising with Application to Differential Privacy](https://mlsanity.com/paper/2209.02043/) (2022)

## Abstract (arXiv)

Given a neighborhood graph representation of a finite set of points xi∈ℝd,i=1,ldots,n, we construct a frame (redundant dictionary) for the space of real-valued functions defined on the graph. This frame is adapted to the underlying geometrical structure of the xi, has finitely many elements, and these elements are localized in frequency as well as in space. This construction follows the ideas of Hammond et al. (2011), with the key point that we construct a tight (or Parseval) frame. This means we have a very simple, explicit reconstruction formula for every function f defined on the graph from the coefficients given by its scalar product with the frame elements. We use this representation in the setting of denoising where we are given noisy observations of a function f defined on the graph. By applying a thresholding method to the coefficients in the reconstruction formula, we define an estimate of f whose risk satisfies a tight oracle inequality.