# Constraint-Based Time-Scale Modification of Music Recordings for Noise Beautification
## 4 Algorithms
### Greedy Algorithm  
We now introduce an efficient greedy algorithm for finding an approximate solution for our mapping problem. This algorithm makes strong assumptions (motivated by our MRI noise beautification scenario) on how the reference and source APs are distributed over time. In our application, the reference APs \(\mathcal{R}=\{r_{1},r_{2},...,r_{M}\}\) (corresponding to the MRI scanner's knocking sounds) are typically spaced in a locally periodic fashion for most of the time. Similarly, the same holds for the source APs \(\mathcal{S}=\{s_{1},s_{2},...,s_{N}\}\) (corresponding to the beats of the music). In other words, there are positive numbers \(\Delta^{\mathcal{R}},\Delta^{\mathcal{S}}\in\mathbb{R}\) such that  
\[r_{m+1}-r_{m}\approx\Delta^{\mathcal{R}}\quad\text{and}\quad s_{n+1}-s_{n} \approx\Delta^{\mathcal{S}} \tag{20}\]  
for most of the \(m\in[1:M-1]\) and \(n\in[1:N-1]\), respectively. Based on this assumption, we define a global scaling factor  
\[\sigma:=\frac{\Delta^{\mathcal{R}}}{\Delta^{\mathcal{S}}}. \tag{21}\]  
Furthermore, we assume that the mapping for the first reference AP \(r_{1}\) is known and equals \(s_{n_{1}}\in\mathcal{S}\) for some \(n_{1}\in[1:N]\). The scaling factor \(\sigma\) and source AP \(s_{n_{1}}\) are used to globally normalize and rescale the source APs:  
\[s_{n}:=\sigma\cdot(s_{n}-s_{n_{1}})+r_{1}. \tag{22}\]  
for \(n\in[1:N]\). Defining \(\varphi(r_{1}):=s_{n_{1}}\), we step through the reference APs and iteratively define \(\varphi(r_{m})\) for \(m=2,3,\ldots,M\). Assuming that \(\varphi(r_{m-1})=s_{n_{m-1}}\) for some \(n_{m-1}\in[1:N]\), we define \(\varphi(r_{m}):=s_{n_{m}}\) with  
\[n_{m}:=\operatorname{argmin}\left\{\left|r_{m}-s_{n}\right|\;\mid\;n\in[n_{m- 1}+1:N]\right\}. \tag{23}\]Note that the condition \(n_{m}>n_{m-1}\) ensures the monotonicity condition of \(\varphi\). Furthermore, note that the greedy algorithm only yields a mapping function if \(n_{m}<N\) for all \(m\in[1:M-1]\). This is typically the case when the number \(N\) of source APs is much larger then the number \(M\) of reference APs.  
Intuitively speaking, using the globally scaled version of source APs (as defined in Equation (21)) compensates for \"tempo differences\" between the reference MRI signal and the source music signal. Furthermore, the minimization in Equation (23) compensates for small local deviations between reference and source APs. In regions of periodically spaced reference APs (with period \(\Delta^{\mathcal{R}}\)) and source APs (with period \(\Delta^{\mathcal{S}}\)), the second-order differences in the resulting mapping is close to zero for most of the time, thus resulting in a low error. Also, this holds if differences between subsequent APs are integer multiples of \(\Delta^{\mathcal{R}}\) and \(\Delta^{\mathcal{S}}\), respectively. Only if there are many local irregularities in the reference or the source, the resulting mapping may yield a poor approximation of the optimal solution. Finally, note that the proposed greedy strategy may be locally refined by the DP-based approach as discussed at the end of Section 4.1.