Decaying sinusoid dictionaries


\(\renewcommand{\var}{\operatorname{Var}} \renewcommand{\dd}{\mathrm{d}} \renewcommand{\pd}{\partial} \renewcommand{\bb}[1]{\mathbb{#1}} \renewcommand{\vv}[1]{\boldsymbol{#1}} \renewcommand{\mm}[1]{\boldsymbol{#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}{\mathop{\mathrm{argmax}}} \renewcommand{\argmin}{\mathop{\mathrm{argmin}}} \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 will 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 will 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 ((???)) in closed form. Substituting in (???) 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}

Inner products of decaying sinusoidal atoms

With the use of (???) 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}\]{#eq:sinusoidproduct}

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.

Normalizing decaying sinusoidal atoms

To use matching pursuit we would need to normalize the atoms in our inner product formula (???).

\[\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 (???), \[\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}

Normalizing decaying sinusoidal molecules

We 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 (???) and to find a (lengthy) closed-form expression for this normalising term.

To file

TBC.

Prony method explained by Sachin Shanbhag and by Sam Pfeiffer.

Barkhuijsen, H., R. de Beer, W. M. J. Bovée, and D. van Ormondt. 1985. “Retrieval of Frequencies, Amplitudes, Damping Factors, and Phases from Time-Domain Signals Using a Linear Least-Squares Procedure.” Journal of Magnetic Resonance (1969) 61 (3): 465–81. https://doi.org/10.1016/0022-2364(85)90187-8.

Cui, Jie, and Dinghui Wang. 2017. “Biosignal Analysis with Matching-Pursuit Based Adaptive Chirplet Transform,” September. https://arxiv.org/abs/1709.08328v1.

Goodwin, Michael. 1997. “Matching Pursuit with Damped Sinusoids.” In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing, 3:2037–40. Munich, Germany: IEEE. https://doi.org/10.1109/ICASSP.1997.599345.

Goodwin, M M, and M Vetterli. 1999. “Matching Pursuit and Atomic Signal Models Based on Recursive Filter Banks.” IEEE Transactions on Signal Processing 47 (7): 1890–1902. https://doi.org/10.1109/78.771038.

Goodwin, M., and M. Vetterli. 1997. “Atomic Decompositions of Audio Signals.” In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997. https://doi.org/10.1109/ASPAA.1997.625601.

Prony, R. 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 2. http://users.polytech.unice.fr/~leroux/PRONY.pdf.

Serra, Xavier, and Julius Smith. 1990. “Spectral Modeling Synthesis: A Sound Analysis/Synthesis System Based on a Deterministic Plus Stochastic Decomposition.” Computer Music Journal 14 (4): 12–24. https://doi.org/10.2307/3680788.