More Like this

1. eGHWT: The Extended Generalized Haar–Walsh Transform

   https://doi.org/10.1007/s10851-021-01064-w  

   Saito, Naoki; Shao, Yiqun (January 2022, Journal of Mathematical Imaging and Vision)

   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 theextendedgeneralized 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” partitionssimultaneously. 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(NlogN)$, whereNis 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$$ ${\left(1.5\right)}^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·{\left(1.84\right)}^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
2. Multiscale transforms for signals on simplicial complexes

   https://doi.org/10.1007/s43670-023-00076-4  

   Saito, Naoki; Schonsheck, Stefan_C; Shvarts, Eugene (December 2023, Sampling Theory, Signal Processing, and Data Analysis)

   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 $$ $\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 $$ $\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
3. Natural Graph Wavelet Packet Dictionaries

   https://doi.org/10.1007/s00041-021-09832-3  

   Cloninger, Alexander; Li, Haotian; Saito, Naoki (June 2021, Journal of Fourier Analysis and Applications)

   null (Ed.)

   Abstract We introduce a set of novel multiscale basis transforms for signals on graphs that utilize their “dual” domains by incorporating the “natural” distances between graph Laplacian eigenvectors, rather than simply using the eigenvalue ordering. These basis dictionaries can be seen as generalizations of the classical Shannon wavelet packet dictionary to arbitrary graphs, and do not rely on the frequency interpretation of Laplacian eigenvalues. We describe the algorithms (involving either vector rotations or orthogonalizations) to construct these basis dictionaries, use them to efficiently approximate graph signals through the best basis search, and demonstrate the strengths of these basis dictionaries for graph signals measured on sunflower graphs and street networks. 

   more » « less
4. A generalized Walsh system for arbitrary matrices

   https://doi.org/10.1515/dema-2019-0006  

   Harding, Steven N.; Picioroaga, Gabriel (January 2019, Demonstratio Mathematica)

   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
5. Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity

   https://doi.org/10.1145/3564246.3585188  

   Alman, Josh; Rao, Kevin (June 2023, STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing)

   We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size N. For the WHT, our new algorithm has an operation count of 23/24N logN + O(N). To our knowledge, this gives the first improvement on the N logN operation count of the simple, folklore Fast Walsh-Hadamard Transform algorithm. For the DFT, our new FFT algorithm uses 15/4N logN + O(N) real arithmetic operations. Our leading constant 15/4 = 3.75 improves on the leading constant of 5 from the Cooley-Tukey algorithm from 1965, leading constant 4 from the split-radix algorithm of Yavne from 1968, leading constant 34/9=3.7777 from a modification of the split-radix algorithm by Van Buskirk from 2004, and leading constant 3.76875 from a theoretically optimized version of Van Buskirk’s algorithm by Sergeev from 2017. Our new WHT algorithm takes advantage of a recent line of work on the non-rigidity of the WHT: we decompose the WHT matrix as the sum of a low-rank matrix and a sparse matrix, and then analyze the structures of these matrices to achieve a lower operation count. Our new DFT algorithm comes from a novel reduction, showing that parts of the previous best FFT algorithms can be replaced by calls to an algorithm for the WHT. Replacing the folklore WHT algorithm with our new improved algorithm leads to our improved FFT. 

   more » « less