Discrete time Fourier and related transforms

Also, chirplets, z-transforms, chromatic derivatives…



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.

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.)

πŸ—

References

Antoniou, Andreas. 2005. Digital signal processing: signals, systems and filters. New York: McGraw-Hill.
Bluestein, L. 1970. β€œA Linear Filtering Approach to the Computation of Discrete Fourier Transform.” IEEE Transactions on Audio and Electroacoustics 18 (4): 451–55.
Box, George E. P., Gwilym M. Jenkins, Gregory C. Reinsel, and Greta M. Ljung. 2016. Time Series Analysis: Forecasting and Control. Fifth edition. Wiley Series in Probability and Statistics. Hoboken, New Jersey: John Wiley & Sons, Inc.
Cochran, W.T., James W. Cooley, D.L. Favin, H.D. Helms, R.A. Kaenel, W.W. Lang, Jr. Maling G.C., D.E. Nelson, C.M. Rader, and Peter D. Welch. 1967. β€œWhat Is the Fast Fourier Transform?” Proceedings of the IEEE 55 (10): 1664–74.
Cooley, J. W., P. A. W. Lewis, and P. D. Welch. 1970. β€œThe Application of the Fast Fourier Transform Algorithm to the Estimation of Spectra and Cross-Spectra.” Journal of Sound and Vibration 12 (3): 339–52.
Gray, Robert M., and Lee D. Davisson. 2010. An Introduction to Statistical Signal Processing. Cambridge: Cambridge University Press.
Griffin, D., and Jae Lim. 1984. β€œSignal Estimation from Modified Short-Time Fourier Transform.” IEEE Transactions on Acoustics, Speech, and Signal Processing 32 (2): 236–43.
Harris, Fredric J. 1978. β€œOn the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform.” Proceedings of the IEEE 66 (1): 51–83.
Hassanieh, Haitham, Piotr Indyk, Dina Katabi, and Eric Price. 2012. β€œNearly Optimal Sparse Fourier Transform.” In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 563–78. STOC ’12. New York, NY, USA: ACM.
Hassanieh, H., P. Indyk, D. Katabi, and E. Price. 2012. β€œSimple and Practical Algorithm for Sparse Fourier Transform.” In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1183–94. Proceedings. Kyoto, Japan: Society for Industrial and Applied Mathematics.
Ignjatovic, A. 2009. β€œChromatic Derivatives and Local Approximations.” IEEE Transactions on Signal Processing 57 (8): 2998–3007.
Ignjatovic, Aleksandar. 2007. β€œLocal Approximations Based on Orthogonal Differential Operators.” Journal of Fourier Analysis and Applications 13 (3): 309–30.
Ignjatovic, Aleksandar, Chamith Wijenayake, and Gabriele Keller. 2018a. β€œChromatic Derivatives and Approximations in Practiceβ€”Part I: A General Framework.” IEEE Transactions on Signal Processing 66 (6): 1498–1512.
β€”β€”β€”. 2018b. β€œChromatic Derivatives and Approximations in Practiceβ€”Part II: Nonuniform Sampling, Zero-Crossings Reconstruction, and Denoising.” IEEE Transactions on Signal Processing 66 (6): 1513–25.
β€”β€”β€”. 2019. β€œChromatic Derivatives and Approximations in Practice (III): Continuous Time MUSIC Algorithm for Adaptive Frequency Estimation in Colored Noise,” 16.
Kay, Steven M. 1993. Fundamentals of Statistical Signal Processing. Prentice Hall Signal Processing Series. Englewood Cliffs, N.J: Prentice-Hall PTR.
Marple, S. Lawrence, Jr. 1987. Digital Spectral Analysis with Applications.
Massar, Serge, and Philippe Spindel. 2008. β€œUncertainty Relation for the Discrete Fourier Transform.” Physical Review Letters 100 (19): 190401.
Moon, Todd K., and Wynn C. Stirling. 2000. Mathematical Methods and Algorithms for Signal Processing. Upper Saddle River, NJ: Prentice Hall.
Narasimha, M. J., A. Ignjatovic, and P. P. Vaidyanathan. 2002. β€œChromatic Derivative Filter Banks.” IEEE Signal Processing Letters 9 (7): 215–16.
Oppenheim, Alan V., Ronald W. Schafer, and John R. Buck. 1999. Discrete-Time Signal Processing. 2nd ed. Upper Saddle River, N.J: Prentice Hall.
Orfanidis, Sophocles J. 1996. Introduction to Signal Processing. Prentice Hall Signal Processing Series. Englewood Cliffs, N.J: Prentice Hall.
Pawar, Sameer, and Kannan Ramchandran. 2015. β€œA Robust Sub-Linear Time R-FFAST Algorithm for Computing a Sparse DFT.” arXiv:1501.00320 [Cs, Math], January.
Prandoni, Paolo, and Martin Vetterli. 2008. Signal processing for communications. Communication and information sciences. Lausanne: EPFL Press.
Rabiner, L., R. Schafer, and C. Rader. 1969. β€œThe Chirp z-Transform Algorithm.” IEEE Transactions on Audio and Electroacoustics 17 (2): 86–92.
Rafii, Z. 2018. β€œSliding Discrete Fourier Transform with Kernel Windowing [Lecture Notes].” IEEE Signal Processing Magazine 35 (6): 88–92.
Smith, Julius O. 2007. Introduction to Digital Filters with Audio Applications. http://www.w3k.org/books/: W3K Publishing.
Stoica, Petre, and Randolph L. Moses. 2005. Spectral Analysis of Signals. 1 edition. Upper Saddle River, N.J: Prentice Hall.
Sukhoy, Vladimir, and Alexander Stoytchev. 2019. β€œGeneralizing the Inverse FFT Off the Unit Circle.” Scientific Reports 9 (1): 1–12.
Therrien, Charles W. 1992. Discrete Random Signals and Statistical Signal Processing. Englewood Cliffs, NJ: Prentice Hall.
Wang, Yu Guang, and Houying Zhu. 2017. β€œLocalized Tight Frames and Fast Framelet Transforms on the Simplex.” arXiv:1701.01595 [Cs, Math], January.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.