An official website of the United States government
Graph signal processing (GSP) is an emerging field developed for analyzing signals defined on irregular spatial structures modeled as graphs. Given the considerable literature regarding the resilience of infrastructure networks using graph theory, it is not surprising that a number of applications of GSP can be found in the resilience domain. GSP techniques assume that the choice of graphical Fourier transform (GFT) imparts a particular spectral structure on the signal of interest. We assess a number of power distribution systems with respect to metrics of signal structure and identify several correlates to system properties and further demonstrate how these metrics relate to performance of some GSP techniques. We also discuss the feasibility of a data-driven approach that improves these metrics and apply it to a water distribution scenario. Overall, we find that many of the candidate systems analyzed are properly structured in the chosen GFT basis and amenable to GSP techniques, but identify considerable variability and nuance that merits future investigation.
more »
« less
The Dual Graph Shift Operator: Identifying the Support of the Frequency Domain
Abstract Contemporary data is often supported by an irregular structure, which can be conveniently captured by a graph. Accounting for this graph support is crucial to analyze the data, leading to an area known as graph signal processing (GSP). The two most important tools in GSP are the graph shift operator (GSO), which is a sparse matrix accounting for the topology of the graph, and the graph Fourier transform (GFT), which maps graph signals into a frequency domain spanned by a number of graph-related Fourier-like basis vectors. This alternative representation of a graph signal is denominated the graph frequency signal. Several attempts have been undertaken in order to interpret the support of this graph frequency signal, but they all resulted in a one-dimensional interpretation. However, if the support of the original signal is captured by a graph, why would the graph frequency signal have a simple one-dimensional support? Departing from existing work, we propose an irregular support for the graph frequency signal, which we coin dual graph. A dual GSO leads to a better interpretation of the graph frequency signal and its domain, helps to understand how the different graph frequencies are related and clustered, enables the development of better graph filters and filter banks, and facilitates the generalization of classical SP results to the graph domain.
more »
« less
- Award ID(s):
- 2008555
- PAR ID:
- 10252129
- Date Published:
- Journal Name:
- Journal of Fourier Analysis and Applications
- Volume:
- 27
- Issue:
- 3
- ISSN:
- 1069-5869
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)The COVID-19 pandemic severely changed the way of life in the United States (US). From early scattered regional outbreaks to current country-wide spread, and from rural areas to highly populated cities, the contagion exhibits diverse patterns at various timescales and locations. We thus conduct a graph frequency analysis to inves- tigate the spread patterns of COVID-19 in different US counties. The commute flows between all 3142 US counties were used to construct a graph capturing the population mobility. The numbers of daily confirmed COVID-19 cases per county were collected and represented as graph signals, which were then mapped into the frequency domain via the graph Fourier transform. The concept of graph frequency in Graph Signal Processing (GSP) enables the decomposition of graph signals (i.e., daily confirmed cases) into modes with smooth or rapid variations with respect to the underlying mobility graph. These different modes of variability are shown to relate to COVID-19 spread patterns within and across counties. Changes in the nature of spread within geographical regions are also revealed by graph frequency analysis at finer temporal scales. Overall, our GSP-based approach leverages case count and mobility data to unveil spatio-temporal contagion patterns of COVID-19 incidence for each US county. Results here support the promising prospect of using GSP tools for epidemiology knowledge discovery on graphs.more » « less
-
The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descrip- tions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal re- construction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction.more » « less
-
Abstract Hyperspectral imaging has broad applications and impacts in areas including environmental science, weather, and geo/space exploration. The intrinsic spectral–spatial structures and potential multi-level features in different frequency bands make multilayer graph an intuitive model for hyperspectral images (HSI). To study the underlying characteristics of HSI and to take the advantage of graph signal processing (GSP) tools, this work proposes a multilayer graph spectral analysis for hyperspectral images based on multilayer graph signal processing (M-GSP). More specifically, we present multilayer graph (MLG) models and tensor representations for HSI. By exploring multilayer graph spectral space, we develop MLG-based methods for HSI applications, including unsupervised segmentation and supervised classification. Our experimental results demonstrate the strength of M-GSP in HSI processing and spectral–spatial information extraction.more » « less
-
Graph signal processing (GSP) techniques are powerful tools that model complex relationships within large datasets, being now used in a myriad of applications in different areas including data science, communication networks, epidemiology, and sociology. Simple graphs can only model pairwise relationships among data which prevents their application in modeling networks with higher-order relationships. For this reason, some efforts have been made to generalize well-known graph signal processing techniques to more complex graphs such as hypergraphs, which allow capturing higher-order relationships among data. In this article, we provide a new hypergraph signal processing framework (t-HGSP) based on a novel tensor-tensor product algebra that has emerged as a powerful tool for preserving the intrinsic structures of tensors. The proposed framework allows the generalization of traditional GSP techniques while keeping the dimensionality characteristic of the complex systems represented by hypergraphs. To this end, the core elements of the t-HGSP framework are introduced, including the shifting operators and the hypergraph signal. The hypergraph Fourier space is also defined, followed by the concept of bandlimited signals and sampling. In our experiments, we demonstrate the benefits of our approach in applications such as clustering and denoising.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00041-021-09850-1
