Quantisation and source-coding for graph signal processing

Abstract

Instead of modelling data on regular domains as in classical 1-D or 2-D signal processing, the field of graph signal processing allows for data to be described and processed on irregular domains such as in sensor networks or in social networks. However, the question of source coding of graph signals on these domains has not been sufficiently addressed in the literature.This thesis introduces and discusses transform coding techniques for graph signals. We focus on nonstationary processes designed by filtering and modulating white noise or via banded frequency correlation matrices. The compression methods are tested in simulations on perturbed random regular graphs, random geometric graphs, and Barabási–Albert graphs. Our simulations show that quantisation quality is related to correlation and sparsity of the transform coefficients.A compression technique that was proposed in literature is found to suffer from numerical instability and high computational complexity. Perfect decorrelation using the Karhunen-Loève transform also has high computational cost. Thus, we propose three compression techniques in three different domains. With the first method, we sample in the vertex domain and recover the signal using bandlimited reconstruction with the quantised samples. This method yields acceptable numerical results only with significant oversampling in scenarios with low vertex-domain correlation.As an alternative, we propose compression in the graph frequency domain. For the nonstationary signal models considered, this method shows the most robust results. Compression quality remains acceptable despite correlation since (especially bandlimited) signals can be sparsely represented. Both techniques approach the rate-distortion limit only in low-rate scenarios. In many scenarios, outliers increase the mean distortion significantly.Motivated by its counterpart in classical signal processing, we introduce the graph Gabor transform (GGT), a sampled version of the windowed graph Fourier transform (GFT). The sampling grid should be matched to the correlation in vertex and frequency domain to obtain less correlated transform coefficients. However, undesirable properties of the GFT impair the grid matching. Moreover, the windowed GFT atoms generally do not form a tight frame and its translation and modulation operators do not have group structure. This limits the use cases of the GGT to high-rate compression scenarios with weakly correlated processes on low-coherence graphs.

Die Graphsignalverarbeitung erlaubt, Daten auf unregelmäßigen Domänen – wie etwa auf Sensor- oder sozialen Netzwerken – darzustellen, anders als in der klassischen 1-D- oder 2-D-Signalverarbeitung. Die Frage der Quellkodierung von Graphsignalen auf diesen Domänen wurde jedoch bisher nicht ausreichend in der Literatur behandelt. In der vorliegenden Arbeit werden Transformationskodierungsverfahren für Graphsignale vorgestellt und diskutiert. Wir richten unser Augenmerk auf nichtstationäre Prozesse, welche wir durch Filterung und Modulation sowie durch bandförmige Frequenzkorrelationsmatrizen konstruieren. Die Kompressionsmethoden werden in Simulationen auf perturbierten zufälligen regulären Graphen, zufälligen geometrischen Graphen und Barabási-Albert-Graphen getestet. Unsere Simulationen zeigen, dass die Quantisierungsqualität von der Korrelation und dem Besetzungsgrad der Transformationskoeffizienten abhängt. Ein in der Literatur vorgeschlagenes Kompressionsverfahren stellt sich als numerisch instabil und rechenaufwändig heraus. Perfekte Dekorrelation mittels der Karhunen- Loève-Transformation ist ebenso mit großem Rechenaufwand verbunden. Daher stellen wir drei Kompressionsverfahren in drei unterschiedlichen Domänen vor. In der ersten Methode tasten wir im Knotenbereich ab und stellen das Signal mittels bandbeschränkter Rekonstruktion unter Verwendung der quantisierten Abtastwerte wieder her. Diese Methode liefert nur mit erheblicher Überabtastung bei schwacher Korrelation im Knotenbereich brauchbare Ergebnisse.Alternativ schlagen wir eine Kompression im Graphfrequenzbereich vor, da dies für die betrachteten nichtstationären Signalmodelle die robustesten Ergebnisse er- zielt. Trotz Korrelation bleibt die Kompressionsqualität annehmbar, da (insbesondere bandbeschränkte) Signale durch dünnbesetzte Koeffizientenvektoren dargestellt werden können. Beide Verfahren kommen der Rate-Distortion-Grenze nur in niederratigen Szenarien nahe. In vielen Fällen erhöhen Ausreißer die mittlere Verzerrung deutlich.Inspiriert von ihrem Pendant in der klassischen Signalverarbeitung führen wir die Graph-Gabor-Transformation (GGT) ein, eine abgetastete Version der gefensterten Graph-Fourier-Transformation (GFT). Das Abtastungsraster sollte an die Korrelation im Knoten- und Frequenzbereich angepasst sein, um schwächer korrelierte Transformationskoeffizienten zu erhalten. Unerwünschte Eigenschaften der GFT beeinträchtigen jedoch die Rasteranpassung. Darüber hinaus bilden weder die gefensterten GFT-Atome einen tight Frame, noch haben ihre Translations- und Modulationsoperatoren Gruppenstruktur. Dies beschränkt den Anwendungsbereich der GGT auf hochratige Kompressionsszenarien mit schwach korrelierten Prozessen auf Graphen mit niedriger Kohärenz.