Decaying sinusoid dictionaries

January 7, 2019 — June 15, 2023

dynamical systems
functional analysis
Hilbert space
linear algebra
signal processing
time series

\[ \renewcommand{\var}{\operatorname{Var}} \renewcommand{\dd}{\mathrm{d}} \renewcommand{\pd}{\partial} \renewcommand{\bb}[1]{\mathbb{#1}} \renewcommand{\vv}[1]{\boldsymbol{#1}} \renewcommand{\mm}[1]{\mathrm{#1}} \renewcommand{\mmm}[1]{\mathrm{#1}} \renewcommand{\cc}[1]{\mathcal{#1}} \renewcommand{\ff}[1]{\mathfrak{#1}} \renewcommand{\oo}[1]{\operatorname{#1}} \renewcommand{\gvn}{\mid} \renewcommand{\II}[1]{\mathbb{I}\{#1\}} \renewcommand{\inner}[2]{\langle #1,#2\rangle} \renewcommand{\Inner}[2]{\left\langle #1,#2\right\rangle} \renewcommand{\argmax}{\operatorname{arg max}} \renewcommand{\argmin}{\operatorname{arg min}} \renewcommand{\omp}{\mathop{\mathrm{OMP}}} \]

Figure 1

Notes on some calculations with decaying sinusoid atoms as a sparse dictionary basis.

Consider an \(L_2\) signal \(f: \bb{R}\to\bb{R}.\) We overload notation and write it with free argument \(\xi\), so that \(f(r\xi-\phi),\) for example, refers to the signal \(\xi\mapsto f(r\xi-\phi).\)

We decompose each \(\hat{G}=\omp_{\cc{S},C}(\cc{A}\{g\})\) in the decaying sinusoid dictionary \[\cc{S}:= \{ \cos (\omega \xi +\phi)e^{ \tau \xi}: \phi,\tau,\omega\in\bb{R}\}.\] {#eq:atomdict} Note that although the original signal is discrete, our decomposition is a continuous near-interpolant for it. There are many methods of fitting decaying sinusoids to series (Prony 1795; Barkhuijsen et al. 1985; Serra and Smith 1990), OMP is convenient in the current application (Michael Goodwin 1997) as we may re-use it in the next stage. Autocorrelograms of musical audio are typically highly sparse, achieving negligible residual error with \(C\leq 4.\)

We apply the OMP with product \(\inner{\cdot}{\cdot}_v\) weighted by \(v(\xi):=\bb{I}\{[0,L)\}(\xi)/L,\) returning parameters \(\{\tau_i, \omega_i, \phi_i\}\) and code weights \(\mu_i\). We first find the normalized code product (@ref(eq:eq:mpproduct)) in closed form. Substituting in @ref(eq:eq:atomdict) gives \[A(r_i(\xi),\{\tau_i, \omega_i, \phi_i\}) = \frac{ \inner{r_i(\xi)}{\cos (\omega_i \xi +\phi_i)e^{\tau_i \xi}}_v }{ \|\cos (\omega_i \xi +\phi_i)e^{\tau_i \xi}\|_v }.(\#eq:atomproduct)\]

Using Euler identities we find the following useful integrals:

\[\begin{aligned} \int^T\cos (\omega t)\exp (-\tau t)\dd t &=\frac{e^{-T \tau } (\omega \sin (T \omega +\phi )-\tau \cos (T \omega +\phi ))}{\tau ^2+\omega ^2} \end{aligned}\] and thus \[\begin{aligned} \int_0^L\cos (\omega t )\exp (-\tau t )\dd t &=\frac{1}{\tau ^2+\omega ^2}\left.e^{- t \tau } (\omega \sin ( t \omega +\phi )-\tau \cos ( t \omega +\phi )) \right|_{ t =0}^{ t =L}\\ &=\exp(-\tau L) \frac{ -\tau \cos (L \omega +\phi ) +\omega \sin (L \omega +\phi ) +\exp(\tau L) ( \tau \cos (\phi ) -\omega \sin (\phi ) ) }{\tau ^2+\omega ^2}\\ &=\frac{1}{\tau ^2+\omega ^2} \left( \tau \cos (\phi ) -\omega \sin (\phi ) - \frac{ \tau \cos (L \omega +\phi ) -\omega \sin (L \omega +\phi ) }{\exp(\tau L)}\right). \end{aligned}(\#eq:sinusoidint)\]

1 Decaying exponentials

A special case.

The classic method for fitting sums-of-exponentials to data is the Prony method (Prony 1795; Barkhuijsen et al. 1985; Serra and Smith 1990), See Prony method explained by Sachin Shanbhag and by Sam Pfeiffer. Ben Coleman, in Fitting Exponential Decay Sums with Positive Coefficients, mentions a more robust special case ESDF (Cantor and Evans 1970; Wiscombe and Evans 1977).

2 Inner products of decaying sinusoidal atoms

With the use of @ref(eq:eq:sinusoidint) we find analytic normalising factors for the atoms.

\[\begin{aligned} &\inner{\cos (\omega \xi + \phi) \exp \tau \xi}{\cos (\omega' \xi' + \phi') \exp \tau' \xi}\\ &= \frac{1}{2} \int v(\xi)\left(\cos(\omega \xi + \phi -\omega' \xi - \phi' )+\cos(\omega \xi + \phi +\omega' \xi' + \phi' ) \right)\exp ((\tau'+\tau) \xi )\dd \xi\\ &= \frac{1}{2} \int v(\xi)\left(\cos((\omega-\omega) \xi + \phi - \phi' ) + \cos((\omega+\omega') \xi + \phi + \phi' ) \right)\exp ((\tau'+\tau) \xi) \dd \xi\\ &= \begin{split} \frac{1}{2} \int v(\xi)\cos((\omega-\omega') \xi + \phi - \phi' ) \exp ((\tau'+\tau) \xi) \dd \xi \\+ \frac{1}{2} \int v(\xi) \cos((\omega+\omega') \xi + \phi + \phi' ) \exp ((\tau'+\tau) \xi) \dd \xi \end{split} \end{aligned}\]

If we choose a “top hat” weight \(v=\bb{I}[0,L],\) it follows that we may expand this

\[\begin{aligned} &\inner{\cos (\omega \xi + \phi) \exp \tau \xi}{\cos (\omega' \xi' + \phi') \exp \tau' \xi}_v\\ &= \begin{split} \frac{1}{2} \int_0^L \cos((\omega-\omega') \xi + \phi - \phi' ) \exp ((\tau'+\tau) \xi) \dd \xi\\ + \frac{1}{2} \int_0^L \cos((\omega+\omega') \xi + \phi + \phi' ) \exp ((\tau'+\tau) \xi) \dd \xi \end{split}\\ &= \begin{split} \frac{1}{2} \left. \frac{e^{-\xi (\tau'+\tau) } \left((\omega-\omega') \sin (\xi (\omega-\omega') +\phi +\phi')-(\tau'+\tau) \cos (\xi (\omega-\omega') +\phi-\phi' )\right)}{(\tau'+\tau)^2+(\omega-\omega')^2} \right|_{\xi=0}^{\xi=L} \\ + \frac{1}{2} \left. \frac{e^{-\xi (\tau'+\tau) } \left((\omega+\omega') \sin (\xi (\omega+\omega') +\phi -\phi')-(\tau'+\tau) \cos (\xi (\omega+\omega') +\phi+\phi' )\right)}{(\tau'+\tau)^2+(\omega+\omega')^2} \right|_{\xi=0}^{\xi=L} \end{split}\\ &= \begin{split} \frac{1}{2} \left. \frac{e^{-\xi \tau_{+} } \left(\omega_{-} \sin (\xi \omega_{-} +\phi_{-} )- \tau_{+} \cos (\xi \omega_{-} + \phi_{-} )\right)}{\tau_{+}^2+\omega_{-}^2} \right|_{\xi=0}^{\xi=L} \\ + \frac{1}{2} \left. \frac{e^{-\xi \tau_{+} } \left(\omega_{+} \sin (\xi \omega_{+} +\phi_{+} )- \tau_{+} \cos (\xi \omega_{+} + \phi_{+} )\right)}{\tau_{+}^2+\omega_{+}^2} \right|_{\xi=0}^{\xi=L} \end{split} \end{aligned}(\#eq:atomproduct) \] where we have defined \(\omega_{+}=\omega+\omega',\) \(\omega_{-}=\omega-\omega'\) etc. This top hat weight is clearly fairly choppy, although it is simple enough to mechanically calculate which is nice.

3 Normalizing decaying sinusoidal atoms

To use matching pursuit we would need to normalize the atoms in our inner product formula @ref(eq:eq:mpproduct).

\[\begin{aligned} \|\cos (\omega \xi + \phi) \exp \tau \xi\|_v^2 &= \int v(\xi) \left(\cos (\omega \xi + \phi) \exp \tau \xi\right)^2 \dd \xi\\ &= \int v(\xi) \cos^2(\omega \xi + \phi) \exp (2\tau \xi)\dd \xi \\ &= \frac{1}{2}\int v(\xi)(1+\cos(2\omega \xi +2\phi)) \exp (-2\tau \xi)\dd \xi\\ \end{aligned}\]

If we choose a top hat weight \(v=\bb{I}[0,L]\) we find, as a special case of @ref(eq:eq:atomproduct), \[\begin{aligned} \|\cos (\omega \xi + \phi) \exp -\tau \xi\|_v^2 &= \int_0^L\left(\cos (\omega \xi + \phi) \exp (-\tau \xi)\right)^2 \dd \xi\\ &= \frac{1}{2}\int_0^L(1+\cos(2\omega \xi +2\phi)) \exp (-2\tau \xi)\dd \xi \\ &=\frac{1}{2}\int_0^L e^{-2 \xi \tau}\cos(2 \xi \omega +2 \phi ) + e^{-2 \xi \tau}\dd \xi\\ &=\frac{1}{2}\int_0^L e^{-2 \xi \tau}\cos(2 \xi \omega +2 \phi ) \dd \xi+ \frac{1}{2}\int_0^L e^{-2 \xi \tau}\dd \xi\\ &=\left. \frac{e^{-2\xi \tau }}{2}\frac{ (\omega \sin (2\xi \omega +2\phi )-\tau \cos (2\xi \omega +2\phi ))}{4\tau ^2+4\omega ^2} \right|_{\xi=0}^{\xi=L} + \frac{1-e^{-2L\tau}}{4 \tau}\\ \end{aligned}(\#eq:atomsquarednorm) \]

4 Normalizing decaying sinusoidal molecules

Now consider a signal \(F\) which is a molecule of decaying sinusoid atoms, in the sense that \(F:\xi\mapsto \sum_{k=1}^K \alpha_k \cos( \omega_k \xi +\phi_k)\exp \tau_k \xi.\) Here we use \(\xi\) as a free argument, as these identities will be applied in the autocorrelation domain.

\[\begin{aligned} \inner{ F}{F} &= \Inner{\sum_k \alpha_k \cos (\omega_k \xi +\phi_k)\exp \tau_k \xi}{\sum_k \alpha_k \cos (\omega_k \xi +\phi)\exp \tau_k \xi} \\ &=\ \sum_{j,k} \alpha_j \alpha_k \Inner{\cos(\omega_j \xi+\phi_j)\exp \tau_j \xi}{\cos(\omega_k \xi+\phi_k)\exp \tau_k\xi} \\ &= 2\sum_{k=1}^K \sum_{j<k} \alpha_j \alpha_k \Inner{\cos(\omega_j \xi+\phi_j)\exp \tau_j \xi}{\cos(\omega_k \xi+\phi_k)\exp \tau_k\xi} + \sum_{k=1}^K \alpha_k^2 \|\cos (\omega_k \xi_k + \phi_k) \exp -\tau_k \xi_k\|^2. \end{aligned}(\#eq:moleculesquarednorm)\]

Once again, choosing \(v=\bb{I}[0,L]\) we can apply @ref(eq:eq:atomsquarednorm) and to find a (lengthy) closed-form expression for this normalising term.

5 Incoming


6 References

Barkhuijsen, de Beer, Bovée, et al. 1985. Retrieval of Frequencies, Amplitudes, Damping Factors, and Phases from Time-Domain Signals Using a Linear Least-Squares Procedure.” Journal of Magnetic Resonance (1969).
Cantor, and Evans. 1970. On Approximation by Positive Sums of Powers.” SIAM Journal on Applied Mathematics.
Cui, and Wang. 2017. Biosignal Analysis with Matching-Pursuit Based Adaptive Chirplet Transform.”
Goodwin, Michael. 1997. Matching Pursuit with Damped Sinusoids.” In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing.
Goodwin, M., and Vetterli. 1997. Atomic Decompositions of Audio Signals.” In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997.
Goodwin, M M, and Vetterli. 1999. Matching Pursuit and Atomic Signal Models Based on Recursive Filter Banks.” IEEE Transactions on Signal Processing.
Prony. 1795. Essai Éxperimental Et Analytique: Sur Les Lois de La Dilatabilité de Fluides Élastique Et Sur Celles de La Force Expansive de La Vapeur de l’alkool, à Différentes Températures.” Journal de l’École Polytechnique Floréal Et Plairial.
Serra, and Smith. 1990. Spectral Modeling Synthesis: A Sound Analysis/Synthesis System Based on a Deterministic Plus Stochastic Decomposition.” Computer Music Journal.
Wiscombe, and Evans. 1977. Exponential-Sum Fitting of Radiative Transmission Functions.” Journal of Computational Physics.