Decaying sinusoid dictionaries
January 7, 2019 — June 14, 2023
Suspiciously similar content
\[ \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}}} \]
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 normalizing 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 normalizing term.
5 Incoming
TBC.