Random Walk Operator-Based Fourier Transform in Connected Directed Acyclic Graphs

Spectral analysis of signals defined on Directed Acyclic Graphs (DAGs) poses significant challenges due to the presence of zero eigenvalues in the adjacency matrix and equivalent shift operators, such as the random walk matrix. This characteristic hinders the differentiation between spectral components of signals on such graphs, rendering conventional spectral analysis impossible. To mitigate this issue, a zero-padding technique for signals defined on DAGs was recently proposed. Given the similarity between the properties of the random walk matrix and the adjacency matrix, this paper explores the feasibility of Fourier analysis using the eigen-decomposition basis of such matrices. The extension of the zero-padding concept to signals on DAGs described by the random walk matrix involves introducing additional nodes connected to the existing structure, with the signal values on these added nodes set to zero. The primary objective of this approach is to facilitate the computation of vertex-domain convolution, thereby enabling the output of graph filters without encountering aliasing issues.