# Correlograms

## Also covariances

This material is revised and expanded from the appendix of draft versions of a recent conference submission, for my own reference. I used (deterministic) correlograms a lot in that, and it was startlingly hard to find a decent summary of their properties anywhere. Nothing new here, but… see the matrial about doing this in a probabilistic way via Wiener-Khintchine representation and covariance kernels which lead to a natural probabilistic spectral analysis.


Consider an $$L_2$$ signal $$f: \bb{R}\to\bb{R}.$$ We will frequently overload notation and refer to as signal with free argument $$t$$, so that $$f(rt-\xi),$$ for example, refers to the signal $$t\mapsto f(rt-\xi).$$ We write the inner product between signals $$t\mapsto f(t)$$ and $$t\mapsto f'(t)$$ as $$\inner{f(t)}{f'(t)}$$. Where it is not clear that the free argument is, e.g. $$t$$, we will annotate it $$\finner{f(t)}{f'(t)}{t}$$.

The correlogram $$\cc{A}:L_2(\bb{R}) \to L_2(\bb{R})$$ maps signals to signals. Specifically, $$\mathcal{A}\{f\}$$ is a signal $$\bb{R}\to\bb{R}$$ such that

$\mathcal{A}\{f\}:=\xi \mapsto \finner{ f(t) }{ f(t-\xi) }{t}$ This is the covariance between $$f(t)$$ and $$f(t-\xi).$$ (Note that we here discuss the covariance between given deterministic signals, not between two stochastic sources; covariance of stochastic processes is a broader, let alone inferring the covariance of stochastic processes.) Note also that this is what I would call an autocovariance not an auto-correlation, since it’s not normalized, but I’ll stick with the latter for now since for reasons of convention.

We derive the properties of this transform.

Multiplication by a constant. Consider a constant $$c\in \bb{R}.$$

\begin{aligned}\mathcal{A}\{cf\}(\xi)&= \inner{ cf(t) }{ cf(t-\xi) }\\ &= c^2\finner{ f(t) }{ f(t-\xi) }{t}\\ &= c^2\mathcal{A}\{f\}(\xi).\\ \end{aligned}

Time scaling:

\begin{aligned}\mathcal{A}\{f(r t)\}(\xi) &=\finner{ f(r t) }{ f(r t-\xi) }{t}\\ &= \int f(r t)f(r t-\xi)\dd t\\ &= \frac{1}{r }\int f(t)f(t-\frac{\xi}{r})\dd t\\ &= \frac{1}{r} \mathcal{A}\{f\}\left(\frac{\xi}{r}\right)\\ \end{aligned}

\begin{aligned}\mathcal{A}\{f+f'\}(\xi) &=\finner{ f(t)+f'(t) }{ f(t-\xi)+f'(t-\xi) }{t}\\ &=\finner{ f(t) }{ f(t-\xi)\rangle+\langle f(t),f'(t-\xi) }{t} +\finner{ f'(t) }{ f(t-\xi)\rangle+\langle f'(t),f'(t-\xi) }{t}\\ &= \mathcal{A}\{f\}(\xi)+ \finner{ f'(t) }{ f(t-\xi)}{t} +\finner{f(t)}{f'(t-\xi) }{t} +\mathcal{A}\{f'\}(\xi).\\ &= \mathcal{A}\{f\}(\xi)+ \finner{ f'(t) }{ f(t-\xi)}{t} +\finner{f(t+\xi)}{f'(t) }{t} +\mathcal{A}\{f'\}(\xi).\\ &= \mathcal{A}\{f\}(\xi)+ \finner{ f'(t) }{ f(t-\xi)}{t} +\finner{f'(t) }{f(t+\xi)}{t} +\mathcal{A}\{f'\}(\xi).\\ \end{aligned}

We can say little about the term $$\finner{ f'(t) }{ f(t-\xi)}+\finner{f'(t) }{f(t+\xi)}{t}$$ without more information about the signals in question. However, we can solve a randomized version. Suppose $$S_i, \, i \in\bb{N}$$ are i.i.d. Rademacher variables, i.e. that they assume a value in $$\{+1,-1\}$$ with equal probability. Then, we can introduce the following property:

\begin{aligned} \bb{E}[ \mathcal{A}\{S_1f + S_2f'\}(\xi) &=\bb{E}[ \mathcal{A}\{S_1f\}(\xi) + \finner{ S_2 f'(t) }{ S_1 f(t-\xi)}{t} +\finner{S_2f'(t) }{S_1 f(t+\xi)}{t} +\mathcal{A}\{S_2f'\}(\xi)]\\ &=\bb{E}[ \mathcal{A}\{S_1f\}(\xi)] + \bb{E}\finner{ S_2 f'(t) }{ S_1 f(t-\xi)}{t} + \bb{E}\finner{S_2f'(t) }{S_1 f(t+\xi)}{t} +\bb{E}[ \mathcal{A}\{S_2f'\}(\xi)]\\ &=\mathcal{A}\{f\}(\xi)+ \bb{E}[ S_1S_2]\finner{ f'(t) }{ f(t-\xi) }{t} + \bb{E}[ S_1S_2]\finner{ f'(t) }{ f(t+\xi) }{t}+\mathcal{A}\{f'\}(\xi)\\ &=\mathcal{A}\{f\}(\xi)+ \mathcal{A}\{f'\}(\xi)\\ \end{aligned}

## References

Bochner, Salomon. 1959. Lectures on Fourier Integrals. Princeton University Press. https://books.google.com?id=MWCYDwAAQBAJ.
Brown, Judith C., and Miller S. Puckette. 1989. “Calculation of a “Narrowed” Autocorrelation Function.” The Journal of the Acoustical Society of America 85 (4, 4): 1595–1601. https://doi.org/10.1121/1.397363.
Cariani, P. A., and B. Delgutte. 1996. “Neural Correlates of the Pitch of Complex Tones. I. Pitch and Pitch Salience.” Journal of Neurophysiology 76 (3, 3): 1698–1716. https://doi.org/10.1152/jn.1996.76.3.1698.
Cheveigné, Alain de, and Hideki Kawahara. 2002. YIN, a Fundamental Frequency Estimator for Speech and Music.” The Journal of the Acoustical Society of America 111 (4, 4): 1917–30. https://doi.org/10.1121/1.1458024.
Kaso, Artan. 2018. “Computation of the Normalized Cross-Correlation by Fast Fourier Transform.” PLOS ONE 13 (9): e0203434. https://doi.org/10.1371/journal.pone.0203434.
Khintchine, A. 1934. “Korrelationstheorie der stationären stochastischen Prozesse.” Mathematische Annalen 109 (1, 1): 604–15. https://doi.org/10.1007/BF01449156.
Langner, Gerald. 1992. “Periodicity Coding in the Auditory System.” Hearing Research 60 (2, 2): 115–42. https://doi.org/10.1016/0378-5955(92)90015-F.
Lewis, J. P. 1995. “Fast Template Matching.” In. Quebec City, Canada: Canadian Image Processing and Pattern Recognition Society,. http://www.scribblethink.org/Work/nvisionInterface/vi95_lewis.pdf.
Licklider, J. C. R. 1951. “A Duplex Theory of Pitch Perception.” Experientia 7 (4, 4): 128–34. https://doi.org/10.1007/BF02156143.
Loynes, R. M. 1968. “On the Concept of the Spectrum for Non-Stationary Processes.” Journal of the Royal Statistical Society. Series B (Methodological) 30 (1): 1–30. https://www.jstor.org/stable/2984457.
Ma, Ning, Phil Green, Jon Barker, and André Coy. 2007. “Exploiting Correlogram Structure for Robust Speech Recognition with Multiple Speech Sources.” Speech Communication 49 (12, 12): 874–91. https://doi.org/10.1016/j.specom.2007.05.003.
Morales-Cordovilla, J. A., A. M. Peinado, V. Sanchez, and J. A. Gonzalez. 2011. “Feature Extraction Based on Pitch-Synchronous Averaging for Robust Speech Recognition.” IEEE Transactions on Audio, Speech, and Language Processing 19 (3): 640–51. https://doi.org/10.1109/TASL.2010.2053846.
Rabiner, L. 1977. “On the Use of Autocorrelation Analysis for Pitch Detection.” IEEE Transactions on Acoustics, Speech, and Signal Processing 25 (1, 1): 24–33. https://doi.org/10.1109/TASSP.1977.1162905.
Slaney, M., and R. F. Lyon. 1990. “A Perceptual Pitch Detector.” In Proceedings of ICASSP, 357–360 vol.1. https://doi.org/10.1109/ICASSP.1990.115684.
Sondhi, M. 1968. “New Methods of Pitch Extraction.” IEEE Transactions on Audio and Electroacoustics 16 (2, 2): 262–66. https://doi.org/10.1109/TAU.1968.1161986.
Tan, L. N., and A. Alwan. 2011. “Noise-Robust F0 Estimation Using SNR-Weighted Summary Correlograms from Multi-Band Comb Filters.” In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 4464–67. https://doi.org/10.1109/ICASSP.2011.5947345.
Wiener, Norbert. 1930. “Generalized Harmonic Analysis.” Acta Mathematica 55: 117–258. https://doi.org/10.1007/BF02546511.

Warning! Experimental comments system! If is does not work for you, let me know via the contact form.