Tight Wavelet Frames on Graphs via Isometric Group Embedding

Rigobert Fokam Souop, Laurent Bitjoka

Spectral graph wavelets apply a kernel to the graph Laplacian spectrum. On an irregular graph their analyzing functions inherit a non-canonical eigenbasis, they do not form a tight frame, and reconstruction requires inverting a frame operator. We take a different route, built on an exact substrate. Given an isometric embedding of a connected graph into a Cayley graph of a finite abelian group, a host on which classical Fourier analysis applies exactly, we construct wavelets on the host and restrict them to the graph. Two constructions arise and we keep them separate. Dilation wavelets use a group automorphism as a dilation, reproducing the classical translate-dilate template but existing only on hosts with composite cyclic factors. Spectral band-pass wavelets use a normalized filter bank in the dual frequency magnitude; they exist on every host, form a Parseval (tight) frame, reconstruct any graph signal exactly via restriction, are translation-covariant, and localize jointly in vertex and frequency. We prove the tight-frame identity and exact reconstruction, give a multiresolution decomposition, and show the full transform costs O(JN log N) via the host fast Fourier transform. For a proper embedding we show the canonical way to complete a signal onto the host remainder is the discrete harmonic extension, which uniquely minimizes the host Dirichlet energy and places the zero-padding and symmetric-extension heuristics as approximations of it. On benchmark hosts reconstruction reaches machine precision and band-pass atoms concentrate 89-99 percent of their energy within graph-distance two of their center.