Non-Negative Dimensionality Reduction in Signal Separation

Abstract

In this thesis, we studied the application of (non-negative) dimensionality reduction methods in signal separation. In single-channel separation, the decomposition techniques as e.g. non-negative matrix factorization (NNMF) or independent component analysis (ICA) are typically applied to time-frequency data of the mixed signal obtained by a signal transform. Starting from this classical separation procedure in the time-frequency domain, we considered an additional preprocessing step, in which the dimension of the data is reduced in order to facilitate the computation. Depending on the separation methods, different properties of the dimensionality reduction technique are required. We focused on the non-negativity of the low-dimensional data or - since the time-frequency data is non-negative - rather on the non-negativity preservation beyond the reduction step, which is mandatory for the application of NNMF. We proposed an approach to non-negative dimensionality reduction that modifies classical dimensionality reduction techniques, which can be written as an optimization problem with rotationally invariant cost functional. By adding a non-negativity constraint to the optimization problem, we enforce the low-dimensional data to be non-negative. If furthermore the reduction map does not increase the angles between data points, these conditions enable us to first solve the classical dimensionality reduction problem before applying a rotation in order to obtain non-negativity of the low-dimensional data set. We discuss the applicability of this splitting approach to different dimensionality reduction techniques, especially to principal component analysis (PCA). For the second step of the splitting approach, a suitable rotation map is needed, which we compute by solving an auxiliary optimization problem on the set of special orthogonal matrices SO(d). This set is not a vector space and thus, standard optimization methods such as steepest descent or Newton’s method are not directly applicable. To overcome the lack of additive update algorithms, we used the Lie group properties of SO(d) in order to construct a multiplicative update algorithm. This construction strongly relies on the exponential map which links SO(d) with its associated Lie algebra. We rigorously derive a steepest descent method on Lie groups, which iterates along curves on the group starting in the direction of a tangent vector. Usually, it is quite difficult to determine such curves explicitly but the structure of a Lie group and the exponential map offer a simple and efficient way to do so. Finally, we discuss the application of the developed non-negative dimensionality reduction techniques to signal separation. We present some numerical results when using our non-negative PCA (NNPCA) and compare its performance with other versions of PCA and different separation techniques, namely NNMF and ICA. From the results, it can be seen that our NNPCA performs better than the rather naive alternative of taking the absolute value of the low-dimensional data set before applying NNMF. Furthermore, the separation with NNPCA in combination with NNMF is almost as good as the one with PCA and ICA.

In der vorliegende Arbeit untersuchten wir die Anwendung von Methoden zur (nichtnegativen) Dimensionsreduktion (NNDR) im Gebiet der Signaltrennung. Typischerweise werden für die Trennung von Monosignalen Zeit-Frequenz-Daten benutzt, die durch eine Signaltransformation aus dem gemischten Signal berechnet werden. Die Trennung selber kann mit Hilfe von verschiedene Methoden wie z. B. nichtnegativer Matrix Faktorisierung (NNMF) oder Independent Component Analysis (ICA) durchgeführt werden. Ausgehend hiervon betrachteten wir einen zusätzlichen Schritt, in welchem die Dimension der Daten im Zeit-Frequenz-Bereich reduziert wird, um Berechnungen zu vereinfachen. In Abhängigkeit von der Trennmethode können unterschiedliche Eigenschaften der Reduktionsmethode im Vordergrund stehen. Weil schon die Zeit-Frequenz-Daten nicht- negativ sind, konzentrierten wir uns auf die Erhaltung der Nichtnegativität der Daten über die Reduktion hinaus, da dies für die Anwendung von NNMF notwendig ist. Wir entwickelten eine Methode zur NNDR, die darauf beruht klassische Reduktionstechniken, welche als Optimierungsproblem (OP) mit rotationsinvariantem Kostenfunktional formuliert werden können, abzuwandeln. Durch Hinzufügen einer Nichtnegativitätsbedingung zu dem OP können wir garantieren, dass die niedrigdimensionalen Daten nichtnegativ sind. Wenn außerdem durch die Reduktion die Winkel zwischen Datenpunkten nicht vergrößert werden, können wir das OP lösen, indem wir erst die klassische Reduktion durchführen und dann die Daten ins Positive rotieren. Überdies diskutierten wir die Anwendbarkeit dieses Splitting Ansatzes auf verschiedene Dimensionsreduktionstechniken, insbesondere auf Principal Component Analysis (PCA). Dieser Ansatz basiert auf einer Rotationsabbildung, die wir durch Lösen eines weiteren OPs auf der speziellen orthogonalen Gruppe SO(d) berechneten. Durch die fehlende Vektorraumstruktur können auf dieser Menge Standardmethoden wie z. B. das Verfahren des steilsten Abstiegs oder das Newtonverfahren nicht ohne Weiteres angewendet werden. Wir können jedoch die Eigenschaften von SO(d) als Lie Gruppe verwenden, um einen multiplikativen Update-Algorithmus zu konstruieren. Diese Konstruktion basiert maßgeblich auf der Exponentialabbildung, die SO(d) mit ihrer assoziierten Lie Algebra verknüpft. Auf Grund dieser Verknüpfung konnten wir ein Verfahren des steilsten Abstiegs auf Lie Gruppen von Grund auf herleiten, bei dem wir entlang von Kurven, die in Richtung eines Tangentialvektors verlaufen, iterieren. Im Allgemeinen ist es nicht leicht solche Kurven explizit zu bestimmen, jedoch bietet die Exponentialabbildung eine einfache und effiziente Möglichkeit hierfür. Schlussendlich diskutierten wir die Anwendung der entwickelten Methoden im Bereich der Signaltrennung. Wir stellten einige numerische Ergebnisse vor und verglichen unsere nichtnegative PCA (NNPCA) mit anderen PCA-Versionen sowie unterschiedlichen Trenntechniken (NNMF und ICA). Die Ergebnisse zeigen, dass unsere NNPCA geeigneter ist als die naive Alternative, bei welcher der Absolutbetrag auf PCA-reduzierte Daten angewendet wird. Des Weiteren zeigte sich, dass die Trennung mit NNPCA und NNMF fast ebenso gute Ergebnisse liefert wie die Trennung mit PCA und ICA.