Nesterov acceleration of the Griffin-Lim Algorithm for phase recovery

Phase recovery refers to the problem of retrieving an unknown time-domain signal from the sole magnitude of its Short-Time Fourier Transform and is a crucial point in signal processing applications including audio synthesis, text to speech synthesis, source separation and timbre transfer. The Griffin-Lim algorithm, published in 1984, is still a key reference to this field. In this thesis we prove that this celebrated method, known as a double projection procedure, is the gradient descent algorithm for a suitable L-Smooth spectral distance measure, and, following the fundamental mathematical result by Nesterov, we then propose a converging accelerated version of it, which we call Nesterov accelerated Griffin-Lim algorithm. This is based on a variable sequence of inertial momenta depending on the number i of iterations. As a corollary of our main theoretical result, applying the locally convex theory, we prove that the rate of convergence to a local minimum value of the spectral distance measure is O(1/i) for the Griffin-Lim algorithm, improved to O(1/i^2) by the proposed method. We compare our Nesterov accelerated Griffin-Lim algorithm with the inertial with constant momentum fast Griffin-Lim algorithm, which is the mostly used enhancement of the original method. Experimental results for the considered signals show that our algorithm obtains higher values in dB of Spectral Signal Noise Ratio. This is valid for initialization of the methods with both random phases and phases with prior signal knowledge, leading to wider gaps in the latter case.

Il problema della ricostruzione di fase consiste nella ricostruzione di un segnale ignoto dalla sola ampiezza della sua trasformata di Fourier ed è un punto cruciale nelle applicazioni di elaborazione dei segnali, comprese la sintesi audio, la sintesi vocale, la separazione di sorgenti e il trasferimento del timbro. L'algoritmo di Griffin-Lim, pubblicato nel 1984, è tuttora quello di riferimento in questo contesto. Nella presente tesi si dimostra che questo celebre metodo, noto come di doppia proiezione, è l'algoritmo di discesa del gradiente di una misura di distanza spettrale con gradiente lipschitziano e, seguendo il fondamentale risultato matematico di Nesterov, ne viene proposto un metodo accelerato convergente che chiamiamo Nesterov accelerated Griffin-Lim algorithm. Esso fa uso di una successione di momenti inerziali variabile col numero i delle iterazioni. Come corollario del risultato teorico principale, applicando la teoria della convessità locale, si dimostra che la velocità di convergenza dell'algoritmo di Griffin-Lim ad un minimo locale della misura di distanza spettrale è O(1/i) mentre quella del metodo proposto si dimostra essere O(1/i^2). La valutazione dell'algoritmo qui introdotto avviene attraverso il confronto con quello inerziale a momento costante di Fast Griffin-Lim che è l'accelerazione più usata del metodo originale. I risultati sperimentali mostrano che nei casi esaminati il metodo proposto è più performante in termini di rapporto segnale rumore spettrale in dB. Questo vale sia inizializzando gli algoritmi con fasi random che attraverso fasi con informazioni a priori sul segnale, portando a divari piu' grandi nel secondo caso.