Harmonic Analysis on Graphs via Isometric Group Embedding: A Canonical Fourier Transform, Shift, and Convolution for Network Signals

Rigobert Fokam Souop, Laurent Bitjoka

Graph signal processing built on the eigenvectors of a Laplacian or adjacency shift inherits three structural compromises: the eigenbasis is fixed only up to rotation within degenerate eigenspaces, the shift is not an isometry, and there is no genuine translation under which filtering is a true convolution. We develop an alternative harmonic analysis that removes all three at once. 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 define a group-embedding graph Fourier transform from the host characters, lift graph signals to the host, and process them there. The characters supply a canonical orthonormal Fourier basis; the group translations form a family of unitary permutation operators obeying an exact group law; and filtering is genuine group convolution, for which the convolution theorem holds as a theorem rather than a definition and which possesses an identity element. We prove the Plancherel, convolution, translation-covariance, and sampling identities in the embedded setting, and compare the shift and convolution operators of the two frameworks side by side. Numerically, the structural identities hold to machine precision; under a same-filter protocol the groupcharacter basis denoises equivalently to the Laplacian eigenbasis once the host complement is filled by a smoothness-respecting extension. The contribution is exact, canonical structure, not a denoising advantage.