An official website of the United States government
Extending computational harmonic analysis tools from the classical setting of regular lattices to the more general setting of graphs and networks is very important and much research has been done recently. Our previous Generalized Haar-Walsh Transform (GHWT) is a multiscale transform for signals on graphs, which is a generalization of the classical Haar and Walsh-Hadamard Transforms. This article proposes the extended Generalized Haar-Walsh Transform (eGHWT). The eGHWT and its associated best-basis selection algorithm for graph signals will significantly improve the performance of the previous GHWT with the similar computational cost, O(N log N) where N is the number of nodes of an input graph. While the previous GHWT/best-basis algorithm seeks the most suitable orthonormal basis for a given task among more than 1.5^N possible bases, the eGHWT/best-basis algorithm can find a better one by searching through more than 0.618 ⋅ (1.84)^N possible bases. This article describes the details of the eGHWT/basis-basis algorithm and demonstrates its superiority using several examples including genuine graph signals as well as conventional digital images viewed as graph signals. Keywords: Multiscale basis dictionaries, wavelets on graphs, graph signal processing, adapted time-frequency analysis, the best-basis algorithm
more »
« less
eGHWT: The Extended Generalized Haar–Walsh Transform
Abstract Extending computational harmonic analysis tools from the classical setting of regular lattices to the more general setting of graphs and networks is very important, and much research has been done recently. The generalized Haar–Walsh transform (GHWT) developed by Irion and Saito (2014) is a multiscale transform for signals on graphs, which is a generalization of the classical Haar and Walsh–Hadamard transforms. We propose the extended generalized Haar–Walsh transform (eGHWT), which is a generalization of the adapted time–frequency tilings of Thiele and Villemoes (1996). The eGHWT examines not only the efficiency of graph-domain partitions but also that of “sequency-domain” partitions simultaneously . Consequently, the eGHWT and its associated best-basis selection algorithm for graph signals significantly improve the performance of the previous GHWT with the similar computational cost, $$O(N \log N)$$ O ( N log N ) , where N is the number of nodes of an input graph. While the GHWT best-basis algorithm seeks the most suitable orthonormal basis for a given task among more than $$(1.5)^N$$ ( 1.5 ) N possible orthonormal bases in $$\mathbb {R}^N$$ R N , the eGHWT best-basis algorithm can find a better one by searching through more than $$0.618\cdot (1.84)^N$$ 0.618 · ( 1.84 ) N possible orthonormal bases in $$\mathbb {R}^N$$ R N . This article describes the details of the eGHWT best-basis algorithm and demonstrates its superiority using several examples including genuine graph signals as well as conventional digital images viewed as graph signals. Furthermore, we also show how the eGHWT can be extended to 2D signals and matrix-form data by viewing them as a tensor product of graphs generated from their columns and rows and demonstrate its effectiveness on applications such as image approximation.
more »
« less
- PAR ID:
- 10330719
- Date Published:
- Journal Name:
- Journal of Mathematical Imaging and Vision
- Volume:
- 64
- Issue:
- 3
- ISSN:
- 0924-9907
- Page Range / eLocation ID:
- 261 to 283
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper we study in detail a variation of the orthonormal bases (ONB) of L2[0, 1] introduced in [Dutkay D. E., Picioroaga G., Song M. S., Orthonormal bases generated by Cuntz algebras, J. Math. Anal. Appl., 2014, 409(2), 1128-1139] by means of representations of the Cuntz algebra ON on L2[0, 1]. For N = 2 one obtains the classic Walsh system which serves as a discrete analog of the Fourier system. We prove that the generalized Walsh system does not always display periodicity, or invertibility, with respect to function multiplication. After characterizing these two properties we also show that the transform implementing the generalized Walsh system is continuous with respect to filter variation. We consider such transforms in the case when the orthogonality conditions in Cuntz relations are removed. We show that these transforms which still recover information (due to remaining parts of the Cuntz relations) are suitable to use for signal compression, similar to the discrete wavelet transform.more » « less
-
Abstract Our previous multiscale graph basis dictionaries/graph signal transforms—Generalized Haar-Walsh Transform (GHWT); Hierarchical Graph Laplacian Eigen Transform (HGLET); Natural Graph Wavelet Packets (NGWPs); and their relatives—were developed for analyzing data recorded on vertices of a given graph. In this article, we propose their generalization for analyzing data recorded on edges, faces (i.e., triangles), or more generally$$\kappa $$ -dimensional simplices of a simplicial complex (e.g., a triangle mesh of a manifold). The key idea is to use the Hodge Laplacians and their variants for hierarchical partitioning of a set of$$\kappa $$ -dimensional simplices in a given simplicial complex, and then build localized basis functions on these partitioned subsets. We demonstrate their usefulness for data representation on both illustrative synthetic examples and real-world simplicial complexes generated from a co-authorship/citation dataset and an ocean current/flow dataset.more » « less
-
Abstract Does every $$n$$-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are $$O(1/\sqrt{n})$$? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every $$n$$-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all $$O(\sqrt{\log n / n})$$, and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon–Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor’s result to nonabelian groups.more » « less
-
We address the problem of learning a sparsifying graph Fourier transform (GFT) for compressible signals on directed graphs (digraphs). Blending the merits of Fourier and dictionary learning representations, the goal is to obtain an orthonormal basis that captures spread modes of signal variation with respect to the underlying network topology, and yields parsimonious representations of bandlimited signals. Accordingly, we learn a data-adapted dictionary by minimizing a spectral dispersion criterion over the achievable frequency range, along with a sparsity-promoting regularization term on the GFT coefficients of training signals. An iterative algorithm is developed which alternates between minimizing a smooth objective over the Stiefel manifold, and soft-thresholding the graph-spectral domain representations of the signals in the training set. A frequency analysis of temperature measurements recorded across the contiguous United States illustrates the merits of the novel GFT design.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1007/s10851-021-01064-w
