2016/07/13 by Calvin Hotchkiss, Hotchkiss, Calvin, Eric Weber +2
Computer Science · Mathematics · #46 #Blind Source Separation Techniques #FOS: Mathematics #Functional Analysis (math.FA) #Mathematical Dynamics and Fractals #Numerical Methods and Algorithms #math.FA #msc:46
paper · pdf · doi:10.48550/arxiv.1607.03690
February Fourier Talks, 2015
arxiv created 2016/07/13 · openalex publication_date 2016/07/13 · arxiv updated 2016/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider finite approximations of a fractal generated by an iterated function system of affine transformations on ℝd as a discrete set of data points. Considering a signal supported on this finite approximation, we propose a Fast (Fractal) Fourier Transform by choosing appropriately a second iterated function system to generate a set of frequencies for a collection of exponential functions supported on this finite approximation. Since both the data points of the fractal approximation and the frequencies of the exponential functions are generated by iterated function systems, the matrix representing the Discrete Fourier Transform (DFT) satisfies certain recursion relations, which we describe in terms of Diţǎ's construction for large Hadamard matrices. These recursion relations allow for the DFT matrix calculation to be reduced in complexity to O(N log N ), as in the case of the classical FFT.