• search hit 2 of 61
Back to Result List

## A Method for Completely Positive and Nonnegative Matrix Factorization

### Eine Methode für Vollständig Positive und Nichtnegative Matrixzerlegungen

• A matrix A is called completely positive if there exists an entrywise nonnegative matrix B such that A = BB^T. These matrices can be used to obtain convex reformulations of for example nonconvex quadratic or combinatorial problems. One of the main problems with completely positive matrices is checking whether a given matrix is completely positive. This is known to be NP-hard in general. rnrnFor a given matrix completely positive matrix A, it is nontrivial to find a cp-factorization A=BB^T with nonnegative B since this factorization would provide a certificate for the matrix to be completely positive. But this factorization is not only important for the membership to the completely positive cone, it can also be used to recover the solution of the underlying quadratic or combinatorial problem.rnrnIn addition, it is not a priori known how many columns are necessary to generate a cp-factorization for the given matrix. The minimal possible number of columns is called the cp-rank of A and so far it is still an open question how to derive the cp-rank for a given matrix. Some facts on completely positive matrices and the cp-rank will be given in Chapter 2.rnrnMoreover, in Chapter 6, we will see a factorization algorithm, which, for a given completely positive matrix A and a suitable starting point, computes the nonnegative factorization A=BB^T. The algorithm therefore returns a certificate for the matrix to be completely positive. As introduced in Chapter 3, the fundamental idea of the factorization algorithm is to start from an initial square factorization which is not necessarily entrywise nonnegative, and extend this factorization to a matrix for which the number of columns is greater than or equal to the cp-rank of A. Then it is the goal to transform this generated factorization into a cp-factorization.rnrnThis problem can be formulated as a nonconvex feasibility problem, as shown in Section 4.1, and solved by a method which is based on alternating projections, as proven in Chapter 6.rnrnOn the topic of alternating projections, a survey will be given in Chapter 5. Here we will see how to apply this technique to several types of sets like subspaces, convex sets, manifolds and semialgebraic sets. Furthermore, we will see some known facts on the convergence rate for alternating projections between these types of sets. Considering more than two sets yields the so called cyclic projections approach. Here some known facts for subspaces and convex sets will be shown. Moreover, we will see a new convergence result on cyclic projections among a sequence of manifolds in Section 5.4.rnrnIn the context of cp-factorizations, a local convergence result for the introduced algorithm will be given. This result is based on the known convergence for alternating projections between semialgebraic sets.rnrnTo obtain cp-facrorizations with this first method, it is necessary to solve a second order cone problem in every projection step, which is very costly. Therefore, in Section 6.2, we will see an additional heuristic extension, which improves the numerical performance of the algorithm. Extensive numerical tests in Chapter 7 will show that the factorization method is very fast in most instances. In addition, we will see how to derive a certificate for the matrix to be an element of the interior of the completely positive cone.rnrnAs a further application, this method can be extended to find a symmetric nonnegative matrix factorization, where we consider an additional low-rank constraint. Here again, the method to derive factorizations for completely positive matrices can be used, albeit with some further adjustments, introduced in Section 8.1. Moreover, we will see that even for the general case of deriving a nonnegative matrix factorization for a given rectangular matrix A, the key aspects of the completely positive factorization approach can be used. To this end, it becomes necessary to extend the idea of finding a completely positive factorization such that it can be used for rectangular matrices. This yields an applicable algorithm for nonnegative matrix factorization in Section 8.2.rnNumerical results for this approach will suggest that the presented algorithms and techniques to obtain completely positive matrix factorizations can be extended to general nonnegative factorization problems.
• Viele nicht konvexe Optimierungsprobleme können als konvexes Problem über dem Kegel der vollständig positiven Matrizen reformuliert werden, sodass für diese Reformulierung lokale und globale Optima zusammenfallen. Dies ist möglich, da die Komplexität des Problems nun vollständig in der Kegelnebenbedingung enthalten ist. Daher ist es nicht verwunderlich, dass die Überprüfung der Zugehörigkeit einer Matrix zum vollständig positiven Kegel NP-schwer ist. Als Hauptresultat dieser Arbeit werden wir sehen, wie algorithmisch ein Zertifikat generiert werden kann, welches für geeignete Startwerte verifiziert, dass eine gegebene Matrix vollständig positiv ist.rnAls fundamentale Definition gilt hier, dass eine Matrix A vollständig positiv ist, falls es eine Zerlegungsmatrix B gibt, die eintragsweise nichtnegativ ist und die Gleichung A=BB^T erfüllt. Eine solche Zerlegung liefert daher immer ein Zertifikat, welches zeigt, dass die gegebene Matrix vollständig positiv ist. Basierend auf dieser Definition werden wir einige Fakten zu diesen Zerlegungen sehen, die nichtzuletzt auch für die praktischen Anwendungen relevant sind und daher durch diese motiviert werden können. Basierend auf diesen Zerlegungen ist es zusätzlich möglich, weitere Bedingungen für vollständig positive Matrizen abzuleiten. Hier ist es insbesondere notwendig mit einer passenden Startzerlegung der Matrix zu beginnen. Wie eine solche Zerlegung generiert werden kann, wird ebenfalls gezeigt. Hier werden wir insbesondere auf orthognale Matrizen als Werkzeug zurückgreifen. So ist es insgesamt möglich, das Problem der Verifizierung der Zugehörigkeit einer Matrix zum vollständig positiven Kegel auf ein Zulässigkeitsproblem zu reduzieren. Im Detail ist es dazu notwendig, eine Matrix im Schnitt eines polyedrischen Kegels und dem nichtnegativen Orthanten zu finden. Dabei werden wir auf die auf von Neumann zurückgehende Technik der alternierenden Projektionen zurückgreifen, um eine solche Matrix zu generieren. Für dieses Verfahren wird eine kurze Einführung und Erläuterung der Anwendung auf verschiedene Typen von Mengen gegeben. Insbesondere werden anhand von geometrischen Eigenschaften bekannte Resultate bezüglich der Konvergenz des Verfahrens und deren Geschwindigkeit gezeigt. Erweitert man die Idee der alternierenden Projektionen auf mehr als zwei Mengen, so spricht man vom zyklischen Projektions-Verfahren. Auch für diesen Ansatz werden bekannte Resultate für Unterräume und allgemeine konvexe Mengen gezeigt. Des Weiteren wird ein neues Konvergenzresultat für die zyklische Projektion zwischen transversalen Mannigfaltigkeiten hergeleitet, welches auf den bekannten Resultaten für die alternierenden Projektionen auf Mannigfaltigkeiten basiert.rnInsbesondere lässt sich die Methode der alternierenden Projektionen auf semialgebraische Mengen anwenden. Dieses Resultat werden wir nutzen, um einen ersten Algorithmus zur Generierung von Zerlegungen von vollständig positiven Matrizen herzuleiten. Für diesen Algorithmus ist es möglich, ein lokales Konvergenzresultat zu zeigen. Insbesondere greift dieser Algorithmus jedoch auf das wiederholte Lösen von second order cone Problemen zurück. Diese sind zwar in polynomieller Zeit lösbar, aber immer noch vergleichsweise rechenintensiv. Aus diesem Grund werden wir eine modifizierte Variante dieses Algorithmus sehen, die ohne diese speziellen Probleme auskommt. Hier verlieren wir zwar das lokale Konvergenzresultat, aber numerische Experimente zeigen, dass dieser Ansatz für nahezu alle getesteten Beispiele vollständig positiver Matrizen in sehr kurzer Zeit eine Zerlegung liefert. Neben der Generierung von Zerlegungen für vollständig positive Matrizen können die gezeigten Methoden und Verfahren auch im Kontext der sogenannten Nichtnegativen Matrix Zerlegung angewandt werden. Hier werden wir sehen, dass für die symmetrische Variante dieser Zerlegung lediglich zusätzliche niedrig-Rang Nebenbedingungen integriert werden müssen. Für den allgemeinen, nicht symmetrischen Fall hingegen können zwar die Ansätze der Verfahren zur Generierung von Zerlegungen für vollständig positive Matrizen verwendet werden, müssen aber auf nicht-quadratische Ausgangsmatrizen erweitert werden. Hier werden wir sehen, dass orthogonale Matrizen nicht mehr das Werkzeug der Wahl sind und entsprechend ersetzt werden müssen. Des Weiteren ist es nicht mehr möglich auf den Ansatz der alternierenden Projektionen zurückzugreifen, da die dazu notwendigen Projektionen nicht mehr berechnet werden können. Nichtsdestotrotz ist es möglich, die Ideen des modifizierten Algorithmus für vollständig positive Matrizen auch in diesem Kontext zu verwenden. Sowohl für den symmetrischen, als auch für den allgemeinen Fall der nichtnegativen Matrixzerlegung, werden wir zahlreiche numerische Experimente sehen, die die Anwendbarkeit der in dieser Arbeit generierten Algorithmen auch in diesem Kontext untermauern.