# Constraint-Based Time-Scale Modification of Music Recordings for Noise Beautification
## 4 Algorithms
### DP-Based Algorithm  
In our first approach, we introduce an algorithm for computing an optimal mapping function using dynamic programming (DP)--an algorithmic paradigm that breaks down a problem intosimpler subproblems in a recursive manner [18]. Let \(\varphi\) be a valid mapping function. Recall from Equation (7) that, for computing the error measure \(\epsilon(\varphi)\), we need second-order differences \(\delta_{2}(r_{m})\) based on the triples \((r_{m},r_{m+1},r_{m+2})\in\mathcal{R}^{3}\) and \((\varphi(r_{m}),\varphi(r_{m+1}),\varphi(r_{m+2}))\in\mathcal{S}^{3}\), \(m\in[1:M-2]\). In our optimization procedure, we consider all possible source triples that may occur in combination with a reference triple. In the following, we specify a source triple by a 3-element ordered subset of \(\mathcal{S}\) with strictly increasing elements:  
\[\gamma=(\gamma(1),\gamma(2),\gamma(3))\in\mathcal{S}^{3}\quad\text{with }\gamma(1)<\gamma(2)<\gamma(3). \tag{9}\]  
Let \(L=\binom{N}{3}\) be the number and \((\gamma_{1},\gamma_{2},\ldots,\gamma_{L})\) the list of all such source triples, where the triples are sorted in lexicographically increasing order, i.e., starting with \(\gamma_{1}=(s_{1},s_{2},s_{3})\) and ending with \(\gamma_{L}=(s_{N-2},s_{N-1},s_{N})\). We say that a family consisting of \(M-2\) source triples specified by a list  
\[(\ell_{1},\ell_{2},\ldots,\ell_{M-2})\quad\text{with}\quad 1\leq\ell_{1}<\ell_{ 2}<\ldots<\ell_{M-2}\leq L \tag{10}\]  
is _valid_ if two subsequent source triples overlap in two points:  
\[\gamma_{\ell_{m}}(2)=\gamma_{\ell_{m+1}}(1)\quad\text{and}\quad\gamma_{\ell_{ m}}(3)=\gamma_{\ell_{m+1}}(2)\quad\text{for }m\in[1:M-3]. \tag{11}\]  
Such a valid family obviously defines a valid mapping function \(\varphi\) by setting:  
\[\varphi(r_{m})= \begin{cases}s_{n}\text{ with }n=\gamma_{\ell_{m}}(1),&\text{ for }m\in[1:M-2],\\ s_{n}\text{ with }n=\gamma_{\ell_{M-2}}(2),&\text{ for }m=M-1,\\ s_{n}\text{ with }n=\gamma_{\ell_{M-2}}(3),&\text{ for }m=M.\end{cases}  \tag{12}\]  
Vice versa, each valid mapping function \(\varphi\) yields a valid family of source triples given by \((\varphi(r_{m}),\varphi(r_{m+1}),\varphi(r_{m+2}))\in\mathcal{S}^{3}\) for \(m\in[1:M-2]\). In other words, there is a one-to-one correspondence between valid mapping functions and valid families of source triples having size \(M-2\). Given a reference triple \((r_{m},r_{m+1},r_{m+2})\) for \(m\in[1:M-2]\) and a source triple \(\gamma_{\ell}\) for \(\ell\in[1:L]\), we define, similar to Equation (6), the second-order difference  
\[\delta_{2}(\ell,m):=\frac{1}{r_{m+1}-r_{m}}\left(\frac{\gamma_{\ell}(3)- \gamma_{\ell}(2)}{r_{m+2}-r_{m+1}}-\frac{\gamma_{\ell}(2)-\gamma_{\ell}(1)}{r _{m+1}-r_{m}}\right). \tag{13}\]  
Furthermore, we define  
\[\epsilon((\ell_{1},\ell_{2},\ldots,\ell_{m})):=\sum_{k=1}^{m}|\delta_{2}(\ell _{k},k)| \tag{14}\]  
for any valid family, specified by \((\ell_{1},\ell_{2},\ldots,\ell_{m})\), of size \(m\in[M-2]\). Obviously, for a family of size \(m=M-2\), this definition leads to the same error measure as defined in Equation (7). With these definitions at hand, we now describe our DP-based algorithm for computing an optimal valid mapping function or, equivalently, an optimal family of source triples of size \(M-2\). To this end, we consider the following subproblem for each \(m\in[M-2]\) and \(\ell\in[1:L]\):  
\[\mathbf{D}(\ell,m):=\min\left\{\epsilon((\ell_{1},\ell_{2},\ldots,\ell_{m})) \ |\ (\ell_{1},\ell_{2},\ldots,\ell_{m})\text{ is valid and }\ell_{m}=\ell\right\}. \tag{15}\]  
In other words, \(\mathbf{D}(\ell,m)\) yields the minimal error for mapping the first \(m\) reference APs \(r_{1},r_{2},\ldots,r_{m}\) to source APs using a valid mapping function with the additional constraint that the last triple is given by \(\gamma_{\ell}\). In the case that such a mapping function does not exist (i.e., that the set in Equation (15) is empty), we set \(\mathbf{D}(\ell,m):=\infty\). The matrix \(\mathbf{D}\in\mathbb{R}^{L\times(M-2)}\) can be computed recursively in a columnwise fashion.