English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In graph signal processing (GSP), data dependencies are represented by a graph whose nodes label the data and the edges capture dependencies among nodes. The graph is represented by a weighted adjacency matrix <inline-formula><tex-math notation="LaTeX">$A$</tex-math></inline-formula> that, in GSP, generalizes the Discrete Signal Processing (DSP) shift operator <inline-formula><tex-math notation="LaTeX">$z^{-1}$</tex-math></inline-formula>. The (right) eigenvectors of the shift <inline-formula><tex-math notation="LaTeX">$A$</tex-math></inline-formula> (graph spectral components) diagonalize <inline-formula><tex-math notation="LaTeX">$A$</tex-math></inline-formula> and lead to a graph Fourier basis <inline-formula><tex-math notation="LaTeX">$F$</tex-math></inline-formula> that provides a graph spectral representation of the graph signal. The inverse of the (matrix of the) graph Fourier basis <inline-formula><tex-math notation="LaTeX">$F$</tex-math></inline-formula> is the Graph Fourier transform (GFT), <inline-formula><tex-math notation="LaTeX">$F^{-1}$</tex-math></inline-formula>. Often, including in real world examples, this diagonalization is numerically unstable. This paper develops an approach to compute an accurate approximation to <inline-formula><tex-math notation="LaTeX">$F$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$F^{-1}$</tex-math></inline-formula>, while insuring their numerical stability, by means of solving a non convex optimization problem. To address the non-convexity, we propose an algorithm, the stable graph Fourier basis algorithm (SGFA) that improves exponentially the accuracy of the approximating <inline-formula><tex-math notation="LaTeX">$F$</tex-math></inline-formula> per iteration. Likewise, we can apply SGFA to <inline-formula><tex-math notation="LaTeX">$A^H$</tex-math></inline-formula> and, hence, approximate the stable left eigenvectors for the graph shift <inline-formula><tex-math notation="LaTeX">$A$</tex-math></inline-formula> and directly compute the GFT. We evaluate empirically the quality of SGFA by applying it to graph shifts <inline-formula><tex-math notation="LaTeX">$A$</tex-math></inline-formula> drawn from two real world problems, the 2004 US political blogs graph and the Manhattan road map, carrying out a comprehensive study on tradeoffs between different SGFA parameters. We also confirm our conclusions by applying SGFA on very sparse and very dense directed Erd&#x0151;s-R&#x00E9;nyi graphs.

Graph Fourier Transform: A Stable Approximation