Spectral methods and orhtogonal basis decompositions

Fourier and friends

Transforming something (let us assume, discrete experimental data rather than abstract mathematical objects) into a new domain, as in the Fourier or Laplace or z-transforms, or a wavelet basis of some kind, usually with a goal of handling some inconveniently curvy data as linear data plus a non-local curvy transformation. This is big in, e.g. signal processing and time series analysis.

Other names: Spectral methods, Hilbert space methods, basis expansions, orthogonal projection methods.

Todo: discuss orthogonal measurements in terms of isometry properties.

Discrete setting

Here I am especially interested in the discrete orthogonal case, by which I mean that we are finding orthogonal bases for signal vectors of countable, often finite, length, e.g. if we are looking at spaces of 1 second of audio at 44kHz, then we consider spaces $\mathbb{R}^{44100}$. If we are looking at RGB webcam images we might consider $\mathbb{R}_+^{640\times 480 \times 3}$. Apparently this case can be related to the continuous case by considering general transforms on Locally Compact Abelian groups, via Pontryagin_duality.

An orthogonal basis requires you to have a domain and inner product specified. If you choose a new inner product, you need a different base to be orthogonal. If you use the machinery of an implicit Hilbert space for a given inner product without troubling to define an explicit form for the “feature space”, you are doing the kernel trick.

See the following course notes

or the texts Rudi17, ReSt00.

Orthogonal basis zoo

• Cousins of the discrete Fourier transform. Mostly a list of things to look up later, since I can’t remember what any of them are right now, and I ran across them when reading about something else. Idk.
• Discrete Hartley transform
• Spherical harmonic transform
• MDCT, which is nearly the DCT. TODO: undertand “nearly”.
• Legendre transform (into Legendre polynomials)
• Bases of disjoint support; the orthogonal bases for non-negative/non-positive data
• Practical: Welch periodograms, and Tukey DTFT

For related ideas, see also

Wavelets

Not (usually) orthogonal. See sparse basis dictionaries.

Refs

AaKa73
Aasnaes, H., & Kailath, T. (1973) An innovations approach to least-squares estimation–Part VII: Some applications of vector autoregressive-moving average models. IEEE Transactions on Automatic Control, 18(6), 601–607. DOI.
AcMc05
Achlioptas, D., & McSherry, F. (2005) On Spectral Learning of Mixtures of Distributions. In P. Auer & R. Meir (Eds.), Learning Theory (pp. 458–469). Springer Berlin Heidelberg DOI.
Adelfio, G., & Schoenberg, F. P.(2009) Point process diagnostics based on weighted second-order statistics and their asymptotic properties. Annals of the Institute of Statistical Mathematics, 61(4), 929–948. DOI.
BoBl07
Bosq, D., & Blanke, D. (2007) Inference and prediction in large dimensions. . Chichester, England ; Hoboken, NJ: John Wiley/Dunod
CaFl11
Carrasco, M., & Florens, J.-P. (2011) Spectral Method for Deconvolving a Density. Econometric Theory, 27(Special Issue 03), 546–581. DOI.
CoLW70
Cooley, J. W., Lewis, P. A. W., & Welch, P. D.(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–352. DOI.
DuBa13
Duarte, M. F., & Baraniuk, R. G.(2013) Spectral compressive sensing. Applied and Computational Harmonic Analysis, 35(1), 111–129. DOI.
DuKa73a
Duttweiler, D., & Kailath, T. (1973a) RKHS approach to detection and estimation problems–IV: Non-Gaussian detection. IEEE Transactions on Information Theory, 19(1), 19–28. DOI.
DuKa73b
Duttweiler, D., & Kailath, T. (1973b) RKHS approach to detection and estimation problems–V: Parameter estimation. IEEE Transactions on Information Theory, 19(1), 29–37. DOI.
Duty16
Dutykh, D. (2016) A brief introduction to pseudo-spectral methods: application to diffusion problems. ArXiv:1606.05432 [Math].
FrKL75
Friedlander, B., Kailath, T., & Ljung, L. (1975) Scattering theory and linear least squares estimation: Part II: Discrete-time problems. In 1975 IEEE Conference on Decision and Control including the 14th Symposium on Adaptive Processes (pp. 57–58). DOI.
Gaba00
Gabardo, J.-P. (2000) Hilbert spaces of distributions having an orthogonal basis of exponentials. Journal of Fourier Analysis and Applications, 6(3), 277–298. DOI.
GaMa06
Gardner, T. J., & Magnasco, M. O.(2006) Sparse time-frequency representations. Proceedings of the National Academy of Sciences, 103(16), 6094–6099. DOI.
GeKa73
Gevers, M., & Kailath, T. (1973) An innovations approach to least-squares estimation–Part VI: Discrete-time innovations representations and recursive estimation. IEEE Transactions on Automatic Control, 18(6), 588–600. DOI.
JBMB00
John, S. E., Boyd, J. P., Marilyn, T., Boyd, J. P., & Eliot, P. T. S.(2000) Chebyshev and Fourier Spectral Methods.
Jone92
Jones, L. K.(1992) A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. The Annals of Statistics, 20(1), 608–613.
Kail71a
Kailath, T. (1971a) A note on least-squares estimation by the innovations method. In 1971 IEEE Conference on Decision and Control (pp. 407–411). DOI.
Kail71b
Kailath, T. (1971b) RKHS approach to detection and estimation problems–I: Deterministic signals in Gaussian noise. IEEE Transactions on Information Theory, 17(5), 530–549. DOI.
Kail74
Kailath, T. (1974) A view of three decades of linear filtering theory. IEEE Transactions on Information Theory, 20(2), 146–181. DOI.
Kailath, T., & Duttweiler, D. (1972) An RKHS approach to detection and estimation problems– III: Generalized innovations representations and a likelihood-ratio formula. IEEE Transactions on Information Theory, 18(6), 730–745. DOI.
KaGe71
Kailath, T., & Geesey, R. (1971) An innovations approach to least squares estimation–Part IV: Recursive estimation given lumped covariance functions. IEEE Transactions on Automatic Control, 16(6), 720–727. DOI.
KaGe73
Kailath, T., & Geesey, R. (1973) An innovations approach to least-squares estimation–Part V: Innovations representations and recursive estimation in colored noise. IEEE Transactions on Automatic Control, 18(5), 435–453. DOI.
KaGW72
Kailath, T., Geesey, R., & Weinert, H. (1972) Some relations among RKHS norms, Fredholm equations, and innovations representations. IEEE Transactions on Information Theory, 18(3), 341–348. DOI.
KaWe75
Kailath, T., & Weinert, H. (1975) An RKHS approach to detection and estimation problems–II: Gaussian signal detection. IEEE Transactions on Information Theory, 21(1), 15–23. DOI.
Kail71c
Kailath, Thomas. (1971c) The Structure of Radon-Nikodym Derivatives with Respect to Wiener and Related Measures. The Annals of Mathematical Statistics, 42(3), 1054–1067.
KeCh72
Kemerait, R., & Childers, D. (1972) Signal detection and extraction by cepstrum techniques. IEEE Transactions on Information Theory, 18(6), 745–759. DOI.
LjKa76
Ljung, L., & Kailath, T. (1976) Backwards Markovian models for second-order stochastic processes (Corresp). IEEE Transactions on Information Theory, 22(4), 488–491. DOI.
LjKF75
Ljung, L., Kailath, T., & Friedlander, B. (1975) Scattering theory and linear least squares estimation: Part I: Continuous-time problems. In 1975 IEEE Conference on Decision and Control including the 14th Symposium on Adaptive Processes (pp. 55–56). DOI.
MGVB11
Mailhé, B., Gribonval, R., Vandergheynst, P., & Bimbot, F. (2011) Fast orthogonal sparse approximation algorithms over local dictionaries. Signal Processing, 91(12), 2822–2835. DOI.
Mikh99
Mikhailenko, B. G.(1999) Spectral Laguerre method for the approximate solution of time dependent problems. Applied Mathematics Letters, 12(4), 105–110. DOI.
MPBB17
Miran, S., Purdon, P. L., Brown, E. N., & Babadi, B. (2017) Sparse spectral estimation from point process observations. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (pp. 841–845). DOI.
MuRe96
Mugglestone, M. A., & Renshaw, E. (1996) A practial guide to the spectral analysis of spatial point processes. Computational Statistics & Data Analysis, 21(1), 43–65. DOI.
OrPe12
Orel, B., & Perne, A. (2012) Computations with half-range Chebyshev polynomials. Journal of Computational and Applied Mathematics, 236(7), 1753–1765. DOI.
Pesa08
Pesaran, B. (2008) Spectral Analysis for Neural Signals. , 10.
ReSt00
Reiter, H., & Stegeman, J. D.(2000) Classical harmonic analysis and locally compact groups. . Courier Corporation
Rudi17
Rudin, W. (2017) Fourier analysis on groups. . Courier Dover Publications
Rust07
Rust, H. (2007) Spectral Analysis of Stochastic Processes. Lecture Notes for the E2C2/CIACS Summer School, Comorova, Romania, University of Potsdam, 1–76.
SeDK75
Segall, A., Davis, M., & Kailath, T. (1975) Nonlinear filtering with counting observations. IEEE Transactions on Information Theory, 21(2), 143–149. DOI.
SeKa76
Segall, A., & Kailath, T. (1976) Orthogonal functionals of independent-increment processes. IEEE Transactions on Information Theory, 22(3), 287–298. DOI.
StMo05
Stoica, P., & Moses, R. L.(2005) Spectral Analysis of Signals. (1 edition.). Upper Saddle River, N.J: Prentice Hall
UnTa14
Unser, M. A., & Tafti, P. (2014) An introduction to sparse stochastic processes. . New York: Cambridge University Press
WaST14
Wang, Y.-X., Smola, A., & Tibshirani, R. J.(2014) The Falling Factorial Basis and Its Statistical Applications. ArXiv:1405.0558 [Stat].
WeKa74a
Weinert, H. L., & Kailath, T. (1974a) Minimum energy control using spline functions. In 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes (pp. 169–172). DOI.
WeKa74b
Weinert, Howard L., & Kailath, T. (1974b) Stochastic Interpretations and Recursive Algorithms for Spline Functions. The Annals of Statistics, 2(4), 787–794. DOI.
WiBö15
Wiatowski, T., & Bölcskei, H. (2015) A Mathematical Theory of Deep Convolutional Neural Networks for Feature Extraction. ArXiv:1512.06293 [Cs, Math, Stat].