Hilbert Transform on Graphs: Let There Be Phase
Chun Hei Michael Chan, Alexandre Cionca, Dimitri Van De Ville · 2024
Read Hilbert Transform on Graphs: Let There Be Phase by Chun Hei Michael Chan, Alexandre Cionca, Dimitri Van De Ville (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18501.txt.
Introduction
Chun Hei Michael Chan, Alexandre Cionca, and Dimitri Van De Ville wrote this signal processing paper, published in 2024. It brings the Hilbert transform, a classic tool that extracts phase from signals, onto data that live on networks rather than on a line.
Phase is half the story of any signal, but graph versions of the Fourier transform stumble on directed networks, whose shift operators cannot be cleanly diagonalized. The authors build on a trick that adds the fewest possible edges to fix that. Those added edges form a cover of cycles, which turns out to be exactly what phase analysis needs. Their generalized transform on the cycle cover recovers the familiar behavior of the classic transform on one loop. The paper gives simple recipes for using phase in graph signals and tests them on examples.
Catalog record
| CREATOR | Chun Hei Michael Chan, Alexandre Cionca, Dimitri Van De Ville |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18501
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hilbert Transform on Graphs: Let There Be Phase Chun Hei Michael Chan, Alexandre Cionca, Dimitri Van De Ville Abstract In the past years, many signal processing operations have been successfully adapted to the graph setting. One elegant and effective approach is to exploit the eigendecomposition of a graph shift operator (GSO), such as the adjacency or Laplacian operator, to define a graph Fourier transform for projecting graph signals on the corresponding basis. However, the extension of this scheme to directed graphs is challenging since the associated GSO is non-symmetric and, in general, not diagonalizable. Here, we build upon a recent framework that adds a minimal number of edges to allow diagonalization of the GSO and thus provide a proper graph Fourier transform. Furthermore, we show that such minimal addition of edges creates a cycle cover and that it is essential for the phase analysis of a signal throughout the graph. Concurrently, we propose a generalization of the Hilbert transform interpreted over the newfound cycle cover, which re-establishes intuitions from traditional Hilbert transform, equivalent to the generalized Hilbert transform on a single cycle. This generalization leads to a number of simple and elegant recipes to effectively exploit the phase information of graph signals provided by the graph Fourier transform. The feasibility of the approach is demonstrated on several examples. I Introduction Graph signal processing (GSP) has emerged as an attractive new methodology for analyzing structured data [ 1 , 2 , 3 ] . In most cases, an undirected graph is considered, which implies a symmetric adjacency matrix. The definition of the graph Fourier transform (GFT) by the eigendecomposition of a graph shift operator (GSO) [ 4 ] , commonly the adjacency or Laplacian matrix, leads then to real-valued eigenvalues and eigenvectors, and constitutes a unitary transform suitable for the analysis and synthesis of graph signals. Different operations, such as filtering, can then be defined and implemented in the spectral graph domain [ 5 , 6 , 7 ] . For directed graphs, however, the eigendecomposition of the GSO leads to complex-valued eigenvalues and eigenvectors. Moreover the GSO itself becomes non-symmetric and is in general non-diagonalizable. While the Jordan normal form (JNF) has been suggested for providing the spectral decomposition of the GSO [ 8 ] , this comes with several complications. First, the JNF is numerically unstable [ 9 ] , especially for larger graphs. Second, non-trivial Jordan blocks correspond to spectral components with dimension larger than one, which impede GSP operations such as filtering and sampling [ 10 ] . Following these two main problems in the numerical application of the JNF in GSP, alternatives have been developed to ensure orthogonality through optimized bases [ 11 , 12 ] . Both these works introduce directed total variation measures and yield real bases. Moreover, [ 12 ] finds bases with uniformly sampled frequency. However, both methods only work on real signals and bypass the GSO, meaning that only spectral operations would be allowed. Another approach proposed is to once again bypass the standard GSO and instead use the diagonalizable Hermitian Laplacian [ 13 ] , which leads to a basis that satisfies Parseval property. These alternatives would fulfill properties such as orthogonality, evenly spread frequencies, and most importantly, diagonizability, but turn out to yield real eigenvalues, preventing the immediate definition of phase defined from complex values. Recent work allows to obtain both properties of diagonalizability and complex-valued eigendecomposition [ 14 ] . Specifically, by leveraging perturbation theory [ 15 , 16 ] on the Jordan blocks, they propose to dismantle non-trivial Jordan blocks that are rank-2 or above, by adding a minimal number of edges to the directed graph. This method enables conventional diagonalization of the modified graph adjacency and thus permits the definition of the GFT as the projection on the dual basis derived from the GSO eigendecomposition. This method also yields a minimally different (spectrally) approximation of the original adjacency matrix [ 14 ] . The new adjacency remains a real-valued matrix that has an eigendecomposition with eigenvalues that are either real-valued or pairs of complex conjugates [ 17 ] . A parallel can thus be drawn between traditional discrete Fourier transform’s (DFT) pairs of conjugate frequencies and the pairs of conjugate eigenvalues found in the presented eigendecomposition of the directed graph. A direct application of this property is the Hilbert transform. Prior work from [ 18 ] defines the graph Hilbert transform (GHT) through JNF, and while they show its equivalence to the traditional Hilbert transform, the authors revert to examples where diagonalizability and invertibility are satisfied, thus not giving a method to apply GHT on general graphs. On a non-diagonalizable graph, as we will see, the GHT through JNF does not provide phase information on all parts of the graph signal. Instead, here we propose using the mentioned minimal graph perturbation to render the GSO diagonalizable and invertible. While [ 14 ] only states that this minimal perturbation add cyclicity in the graph, we prove that it creates a cycle cover. Furthermore, we show through a simple example that such a cycle cover is essential for phase analysis throughout the graph. Leveraging this newfound cycle cover, we introduce a more intuitive and familiar definition of the GHT, providing interpretation for instantaneous phase and amplitude on cycles as in traditional HT. Finally we highlight its properties and specifically the extension to the graph analytical signal by insightful examples. II Background In what follows, we denote a matrix \bf X as bold uppercase and a vector \bf x as bold lowercase. An element k of a vector will be indicated as {\bf x}[k] and a series of vectors {\bf x}_{m} will be indexed using subscript. The conjugate will be written as \cdot^{\star} . Let us consider a directed graph \mathcal{G}=(V,E) , with V being the set of nodes and E the set of edges. The directed graph \mathcal{G} has N nodes and is also characterized by the (non-symmetric) adjacency matrix {\bf A} . In [ 14 ] , the perturbed GSO is obtained by adding iteratively rank-1 matrices (i.e., single edges) to \bf A . On each iteration, the largest Jordan block is identified by considering the group of the largest number of collinear Jordan eigenvectors. Using [ 14 , Th. 4, Lem. 12] a candidate edge to dismantle a Jordan block is an edge (n,m) such that \left|{\bf t}[n]\right|\left|{\bf q}[m]\right|\neq 0 , with \bf{t} and \bf{q} one of the left and right eigenvectors associated to the largest Jordan block, respectively. The same criterion is used on eigenvectors associated to the eigenvalue 0. At the end, the process yields a graph \mathcal{G}^{\prime}=(V,E^{\prime}) with associated adjacency {\bf A}^{\prime} that is guaranteed to be diagonalizable and invertible. III From Graph Phase to Hilbert Transform III-A Phase in the Graph Fourier Domain Let us consider the eigendecomposition of the perturbed adjacency: {\bf A^{\prime}}={\bf U}{\bf\Lambda}{\bf U}^{-1}, where the eigenvalues {\bf\Lambda}[k,k]=\lambda_{k} are either real-valued with corresponding real-valued eigenvectors {\bf u}_{k} , k=1,\ldots,N , that are the columns of {\bf U} ; or complex-valued, and then come in pairs of complex conjugate eigenvalues and eigenvectors [ 17 ] . For instance, for a pair of complex-valued eigenvalues with indexes (k_{1},k_{2}) , we have \lambda_{k_{1}}=\lambda_{k_{2}}\!^{\star}