# 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}}}$

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 , OMP is convenient in the current application 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 , 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 .

## 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.

TBC.

## 6 References

Barkhuijsen, de Beer, Bovée, et al. 1985. Journal of Magnetic Resonance (1969).
Cantor, and Evans. 1970. SIAM Journal on Applied Mathematics.
Cui, and Wang. 2017.
Goodwin, Michael. 1997. In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing.
Goodwin, M., and Vetterli. 1997. In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997.
Goodwin, M M, and Vetterli. 1999. IEEE Transactions on Signal Processing.
Prony. 1795. Journal de l’École Polytechnique Floréal Et Plairial.
Serra, and Smith. 1990. Computer Music Journal.
Wiscombe, and Evans. 1977. Journal of Computational Physics.