Tight local graph Fourier frames with finite support

Abstract

The application of graph signal processing (GSP) methods to large-scale real-world problems has often been hampered by a high computational complexity. We therefore address the problem of designing a computationally efficient and intuitively meaningful graph signal transformation that can serve as a workhorse for a variety of GSP tasks and as an alternative to the classical graph Fourier transform. To that end, we introduce the concept of local graph Fourier frames (LGFFs), i.e., redundant bases that build on graph Fourier transforms restricted to subgraphs. We provide theoretical results regarding the existence of tight (Parseval) LGFFs, discuss simple designs that entail LGFFs with finite support, study desirable properties of LGFF, and discuss an application example in the context of graph signal denoising.