  We propose two-channel critically-sampled filter banks for signals on
undirected graphs that utilize spectral domain sampling. Unlike conventional
approaches based on vertex domain sampling, our transforms have the following
desirable properties: 1) perfect reconstruction regardless of the
characteristics of the underlying graphs and graph variation operators and 2) a
symmetric structure; i.e., both analysis and synthesis filter banks are built
using similar building blocks. Along with the structure of the filter banks,
this paper also proves the general criterion for perfect reconstruction and
theoretically shows that the vertex and spectral domain sampling coincide for a
special case. The effectiveness of our approach is evaluated by comparing its
performance in nonlinear approximation and denoising with various conventional
graph transforms.
