Discrete time Fourier and related transforms

Also, chirplets, z-transforms, chromatic derivatives…

October 17, 2019 — October 17, 2019

convolution
functional analysis
Hilbert space
nonparametric
signal processing
sparser than thou

Care and feeding of Discrete Fourier transforms (DTFT), especially Fast Fourier Transforms, and other operators on discrete time series. Complexity results, timings, algorithms, properties. These are useful in a vast number of applications, such as filter design, time series analysis, various nifty optimisations of other algorithms etc.

1 Chirp z-transform

Chirplets, one-sided discrete Laplace transform related to damped sinusoid representation. (Bluestein 1970; Rabiner, Schafer, and Rader 1969)

A recent publication (Sukhoy and Stoytchev 2019) shows that these are as tractable as FFTs to invert, which is to say, very. I will read the paper and see if that is as useful to me as it seems like it might be. (The paper has a lot of elementary proofreading errors, which is a bad start.)

🏗

2 Windowing the DTFT

(Harris 1978; Cooley, Lewis, and Welch 1970; Rafii 2018)

🏗

3 Chromatic derivatives

(Narasimha, Ignjatovic, and Vaidyanathan 2002; Aleksandar Ignjatovic 2007; A. Ignjatovic 2009; Aleksandar Ignjatovic, Wijenayake, and Keller 2018b, 2019, 2018b)

🏗

4 References

Antoniou. 2005. Digital signal processing: signals, systems and filters.
Bluestein. 1970. “A Linear Filtering Approach to the Computation of Discrete Fourier Transform.” IEEE Transactions on Audio and Electroacoustics.
Box, Jenkins, Reinsel, et al. 2016. Time Series Analysis: Forecasting and Control. Wiley Series in Probability and Statistics.
Cochran, Cooley, Favin, et al. 1967. “What Is the Fast Fourier Transform?” Proceedings of the IEEE.
Cooley, Lewis, and Welch. 1970. “The Application of the Fast Fourier Transform Algorithm to the Estimation of Spectra and Cross-Spectra.” Journal of Sound and Vibration.
Gray, and Davisson. 2010. An Introduction to Statistical Signal Processing.
Griffin, and Lim. 1984. “Signal Estimation from Modified Short-Time Fourier Transform.” IEEE Transactions on Acoustics, Speech, and Signal Processing.
Harris. 1978. “On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform.” Proceedings of the IEEE.
Hassanieh, Haitham, Indyk, Katabi, et al. 2012. “Nearly Optimal Sparse Fourier Transform.” In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing. STOC ’12.
Hassanieh, H., Indyk, Katabi, et al. 2012. “Simple and Practical Algorithm for Sparse Fourier Transform.” In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings.
Ignjatovic, Aleksandar. 2007. “Local Approximations Based on Orthogonal Differential Operators.” Journal of Fourier Analysis and Applications.
Ignjatovic, A. 2009. “Chromatic Derivatives and Local Approximations.” IEEE Transactions on Signal Processing.
Ignjatovic, Aleksandar, Wijenayake, and Keller. 2018a. “Chromatic Derivatives and Approximations in Practice—Part I: A General Framework.” IEEE Transactions on Signal Processing.
———. 2018b. “Chromatic Derivatives and Approximations in Practice—Part II: Nonuniform Sampling, Zero-Crossings Reconstruction, and Denoising.” IEEE Transactions on Signal Processing.
———. 2019. “Chromatic Derivatives and Approximations in Practice (III): Continuous Time MUSIC Algorithm for Adaptive Frequency Estimation in Colored Noise.”
Kay. 1993. Fundamentals of Statistical Signal Processing. Prentice Hall Signal Processing Series.
Marple. 1987. Digital Spectral Analysis with Applications.
Massar, and Spindel. 2008. “Uncertainty Relation for the Discrete Fourier Transform.” Physical Review Letters.
Moon, and Stirling. 2000. Mathematical Methods and Algorithms for Signal Processing.
Narasimha, Ignjatovic, and Vaidyanathan. 2002. “Chromatic Derivative Filter Banks.” IEEE Signal Processing Letters.
Oppenheim, Schafer, and Buck. 1999. Discrete-Time Signal Processing.
Orfanidis. 1996. Introduction to Signal Processing. Prentice Hall Signal Processing Series.
Pawar, and Ramchandran. 2015. “A Robust Sub-Linear Time R-FFAST Algorithm for Computing a Sparse DFT.” arXiv:1501.00320 [Cs, Math].
Prandoni, and Vetterli. 2008. Signal processing for communications. Communication and information sciences.
Rabiner, Schafer, and Rader. 1969. “The Chirp z-Transform Algorithm.” IEEE Transactions on Audio and Electroacoustics.
Rafii. 2018. “Sliding Discrete Fourier Transform with Kernel Windowing [Lecture Notes].” IEEE Signal Processing Magazine.
Smith. 2007. Introduction to Digital Filters with Audio Applications.
Stoica, and Moses. 2005. Spectral Analysis of Signals.
Sukhoy, and Stoytchev. 2019. “Generalizing the Inverse FFT Off the Unit Circle.” Scientific Reports.
Therrien. 1992. Discrete Random Signals and Statistical Signal Processing.
Wang, and Zhu. 2017. “Localized Tight Frames and Fast Framelet Transforms on the Simplex.” arXiv:1701.01595 [Cs, Math].