Orthogonal Fourier Analysis on Directed Acyclic Graphs via Möbius Total Variation

Signal processing on directed acyclic graphs (DAGs) presents unique challenges. Unlike for undirected graphs, the Laplacian matrix of a DAG lacks a complete eigenbasis in general, and the corresponding adjacency matrix never has one, which prevents the use of conventional graph Fourier analysis. To address these challenges, in this work we propose the first orthogonal Fourier basis that is specifically designed for DAGs, referred to as the Möbius basis. This basis is derived from our novel concept of Möbius total variation (Möbius TV) for DAGs, a generalization of the classical definition of TV in discrete time, which also constitutes a DAG. We then develop two variants of the Möbius basis, which have desirable properties with respect to constant signals. We validate the effectiveness of our Fourier basis against a comprehensive set of prior proposed bases for directed graphs through three types of experiments, considering both synthetic and real-world DAGs and DAG signals.