Energy Compaction Filters on Graphs

Abstract

In classical signal processing spectral concentration is an important problem that was first formulated and analyzed by Slepian. The solution to this problem gives the optimal FIR filter that can confine the largest amount of energy in a specific bandwidth for a given filter order. The solution is also known as the prolate sequence. This study investigates the same problem for polynomial graph filters. The problem is formulated in both graph-free and graph-dependent fashions. The graph-free formulation assumes a continuous graph spectrum, in which case it becomes the polynomial concentration problem. This formulation has a universal approach that provides a theoretical reference point. However, in reality graphs have discrete spectrum. The graph-dependent formulation assumes that the eigenvalues of the graph are known and formulates the energy compaction problem accordingly. When the eigenvalues of the graph have a uniform distribution, the graph-dependent formulation is shown to be asymptotically equivalent to the graph-free formulation. However, in reality eigenvalues of a graph tend to have different densities across the spectrum. Thus, the optimal filter depends on the underlying graph operator, and a filter cannot be universally optimal for every graph.