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.)
🏗
Chromatic derivatives
(Narasimha, Ignjatovic, and Vaidyanathan 2002; Aleksandar Ignjatovic 2007; A. Ignjatovic 2009; Aleksandar Ignjatovic, Wijenayake, and Keller 2018b, 2019, 2018a)
🏗
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. https://doi.org/10.1109/TAU.1970.1162132.
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. https://doi.org/10.1109/PROC.1967.5957.
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. https://doi.org/10.1016/0022-460X(70)90076-3.
Gray, Robert M., and Lee D. Davisson. 2010. An Introduction to Statistical Signal Processing. Cambridge: Cambridge University Press. https://ee.stanford.edu/ gray/sp.html.
Griffin, D., and Jae Lim. 1984. “Signal Estimation from Modified Short-Time Fourier Transform.” IEEE Transactions on Acoustics, Speech, and Signal Processing 32 (2, 2): 236–43. https://doi.org/10.1109/TASSP.1984.1164317.
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. https://doi.org/10.1109/PROC.1978.10837.
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. http://groups.csail.mit.edu/netmit/sFFT/soda_paper.pdf.
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. https://doi.org/10.1145/2213977.2214029.
Ignjatovic, A. 2009. “Chromatic Derivatives and Local Approximations.” IEEE Transactions on Signal Processing 57 (8): 2998–3007. https://doi.org/10.1109/TSP.2009.2020749.
Ignjatovic, Aleksandar. 2007. “Local Approximations Based on Orthogonal Differential Operators.” Journal of Fourier Analysis and Applications 13 (3): 309–30. https://doi.org/10.1007/s00041-006-6085-y.
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. https://doi.org/10.1109/TSP.2017.2787127.
———. 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. https://doi.org/10.1109/TSP.2017.2787149.
———. 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. http://adsabs.harvard.edu/abs/1987ph...book.....M.
Massar, Serge, and Philippe Spindel. 2008. “Uncertainty Relation for the Discrete Fourier Transform.” Physical Review Letters 100 (19): 190401. https://doi.org/10.1103/PhysRevLett.100.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. https://doi.org/10.1109/LSP.2002.801720.
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. http://www.ece.rutgers.edu/ orfanidi/intro2sp/orfanidis-i2sp.pdf.
Pawar, Sameer, and Kannan Ramchandran. 2015. “A Robust Sub-Linear Time R-FFAST Algorithm for Computing a Sparse DFT.” January 1, 2015. http://arxiv.org/abs/1501.00320.
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. https://doi.org/10.1109/TAU.1969.1162034.
Rafii, Z. 2018. “Sliding Discrete Fourier Transform with Kernel Windowing [Lecture Notes].” IEEE Signal Processing Magazine 35 (6, 6): 88–92. https://doi.org/10.1109/MSP.2018.2855727.
Smith, Julius O. 2007. Introduction to Digital Filters with Audio Applications. http://www.w3k.org/books/: W3K Publishing. https://ccrma.stanford.edu/ jos/filters/filters.html.
Stoica, Petre, and Randolph L. Moses. 2005. Spectral Analysis of Signals. 1 edition. Upper Saddle River, N.J: Prentice Hall. http://user.it.uu.se/ ps/SAS-new.pdf.
Sukhoy, Vladimir, and Alexander Stoytchev. 2019. “Generalizing the Inverse FFT Off the Unit Circle.” Scientific Reports 9 (1): 1–12. https://doi.org/10.1038/s41598-019-50234-9.
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.” January 6, 2017. http://arxiv.org/abs/1701.01595.