When Slepian Meets Fiedler

Putting a Focus on the Graph Spectrum

D. Van De Ville, R. Demesmaeker, M. G. Preti, "When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum", IEEE Signal Processing Letters, 24(7):1001-1004, 2017.

David S. Slepian (1923-2007) is highly recognized in the signal processing community for his seminal work on prolate spheroidal wave functions, today commonly called “Slepians”. These functions strike a balance between localization in the original (temporal or spatial) domain and the spectral (Fourier) domain. They also constitute an orthogonal, bandlimited basis with maximal energy concentration in a preselected interval, and satisfy many elegant mathematical properties.

Miroslav Fiedler (1926-2015) is well known for his contributions to algebraic graph theory. The eigenvector of the graph Laplacian with smallest non-zero eigenvalue is named the “Fiedler vector” and plays a key role in the solution of many graph problems, such as Laplacian embedding and graph clustering.

As a tribute to these bright minds and their impact on modern signal processing, we propose the design of bandlimited graph signals that maximize energy in a subgraph as the graph equivalent of Slepians. Then, we use this concept to generalize Laplacian embedding and graph clustering. This allows to “focus” the graph spectrum to a given subgraph with the aim of minimizing a generalized Laplacian embedding/graph-cut criterion. We illustrate the feasibility of the proposed graph Slepian designs with a practical example. This development can serve several future research avenues in graph signal processing, multi-resolution transforms, uncertainty principles, and hierarchical clustering, just to name a few.