More Like this

1. The extended generalized Haar-Walsh transform and applications

   https://doi.org/10.1117/12.2528923  

   Shao, Yiqun; Saito, Naoki (September 2019, Wavelets and Sparsity XVIII)

   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
2. Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations

   Dao, Tri; Gu, Albert; Eichhorn, Matthew; Rudra, Atri; Re, Christopher (June 2019, Proceedings of Machine Learning Research)

   Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (subquadratic) algorithm. We ask to what extent hand-crafting these algorithms and implementations is necessary, what structural prior they encode, and how much knowledge is required to automatically learn a fast algorithm for a provided structured transform. Motivated by a characterization of fast matrix-vector multiplication as products of sparse matrices, we introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of transforms. This generic formulation can automatically learn an efficient algorithm for many important transforms; for example, it recovers the O(N logN) Cooley-Tukey FFT algorithm to machine precision, for dimensions N up to 1024. Furthermore, our method can be incorporated as a lightweight replacement of generic matrices in machine learning pipelines to learn efficient and compressible transformations. On a standard task of compressing a single hidden-layer network, our method exceeds the classification accuracy of unconstrained matrices on CIFAR-10 by 3.9 points—the first time a structured approach has done so—with 4X faster inference speed and 40X fewer parameters. 

   more » « less
3. Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation

   Aggarwal, Amol and (July 2022, Computational complexity)

   Polynomial approximations for e−x and ex have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for n sample points in Θ(logn) dimensions with error δ=n−Θ(1). We show that the running time one can achieve depends on the square of the diameter of the point set, B, with a transition at B=Θ(logn) mirroring the corresponding transition in dB;δ(e−x): - When B=o(logn), we give the first algorithm running in time n1+o(1). - When B=κlogn for a small constant κ>0, we give an algorithm running in time n1+O(loglogκ−1/logκ−1). The loglogκ−1/logκ−1 term in the exponent comes from analyzing the behavior of the leading constant in our computation of dB;δ(e−x). - When B=ω(logn), we show that time n2−o(1) is necessary assuming SETH. 

   more » « less
4. 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
5. Low-Span Parallel Algorithms for the Binary-Forking Model

   https://doi.org/10.1145/3409964.3461802  

   Ahmad, Zafar; Chowdhury, Rezaul; Das, Rathish; Ganapathi, Pramod; Gregory, Aaron; Javanmard, Mohammad Mahdi (January 2021, Proc. 33st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA))

   null (Ed.)

   The binary-forking model is a parallel computation model, formally defined by Blelloch et al., in which a thread can fork a concurrent child thread, recursively and asynchronously. The model incurs a cost of Theta(log n) to spawn or synchronize n tasks or threads. The binary-forking model realistically captures the performance of parallel algorithms implemented using modern multithreaded programming languages on multicore shared-memory machines. In contrast, the widely studied theoretical PRAM model does not consider the cost of spawning and synchronizing threads, and as a result, algorithms achieving optimal performance bounds in the PRAM model may not be optimal in the binary-forking model. Often, algorithms need to be redesigned to achieve optimal performance bounds in the binary-forking model and the non-constant synchronization cost makes the task challenging. In this paper, we show that in the binary-forking model we can achieve optimal or near-optimal span with negligible or no asymptotic blowup in work for comparison-based sorting, Strassen's matrix multiplication (MM), and the Fast Fourier Transform (FFT). Our major results are as follows: (1) A randomized comparison-based sorting algorithm with optimal O(log n) span and O(nlog n) work, both w.h.p. in n. (2) An optimal O(log n) span algorithm for Strassen's matrix multiplication (MM) with only a loglog n - factor blow-up in work as well as a near-optimal O(log n loglog log n) span algorithm with no asymptotic blow-up in work. (3) A near-optimal O(log n logloglog n) span Fast Fourier Transform (FFT) algorithm with less than a log n-factor blow-up in work for all practical values of n (i.e., n le 10 ^10,000 ). 

   more » « less