Robust Low-Rank Approximation of Matrices in lp-Space

Low-rank approximation plays an important role in many areas of science and engineering such as signal/image processing, machine learning, data mining, imaging, bioinformatics, pattern classification and computer vision because many real-world data exhibit low-rank property. This dissertation devises advanced algorithms for robust low-rank approximation of a single matrix as well as multiple matrices in the presence of outliers, where the conventional dimensionality reduction techniques such as the celebrated principal component analysis (PCA) are not applicable. The proposed methodology is based on minimizing the entry-wise $\ell_p$-norm of the residual including the challenging nonconvex and nonsmooth case of $p<1$. Theoretical analyses are also presented. Extensive practical applications are discussed. Experimental results demonstrate that the superiority of the proposed methods over the state-of-the-art techniques.

Two iterative algorithms are designed for low-rank approximation of a single matrix. The first is the iteratively reweighted singular value decomposition (IR-SVD), where the SVD of a reweighted matrix is performed at each iteration. The second converts the nonconvex $\ell_p$-matrix factorization into a series of easily solvable $\ell_p$-norm minimization with vectors being variables. Applications to image demixing, foreground detection in video surveillance, array signal processing, and direction-of-arrival estimation for source localization in impulsive noise are investigated.

The low-rank approximation with missing values, i.e., robust matrix completion, is also addressed. Two algorithms are developed for it. The first iteratively solves a set of linear $\ell_p$-regression problems while the second applies the alternating direction method of multipliers (ADMM) in the $\ell_p$-space. At each iteration of the ADMM, it requires performing a least squares (LS) matrix factorization and calculating the proximity operator of the $p$th power of the $\ell_p$-norm. The LS factorization is efficiently solved using linear LS regression while the proximity operator is obtained by root finding of a scalar nonlinear equation. The two proposed algorithms are scalable to the problem size. Applications to recommender systems, collaborative filtering, and image inpainting are provided.

The $\ell_p$-greedy pursuit ($\ell_p$-GP) algorithms are devised for joint robust low-rank approximation of multiple matrices (RLRAMM) with outliers. The $\ell_p$-GP with $0

Low-Rank Approximationen spielen eine bedeutende Rolle in vielen Bereichen der Wissenschaft und Technik, wie zum Beispiel in der Signal- und Bildverarbeitung, im maschinellen Lernen und Data Mining, sowie in der Bildgebung, der Bioinformatik, der Musterklassifizierung und im Bereich Computer Vision. Grund hierfür ist, dass viele Daten, die realen Anwendungsgebieten entstammen, von Natur aus niederrangig sind.

Ziel dieser Dissertation ist die Entwicklung neuer Algorithmen zur robusten Low-Rank Approximation einzelner und mehrerer Matrizen in Gegenwart von Ausreiß ern---einem Problem bei dem konventionelle Techniken der Dimensionalitätsreduktion wie beispielsweise die Hauptkomponentenanalyse (engl. principial component analysis, PCA) häufig versagen. Die in dieser Arbeit vorgestellte Methodik basiert auf einer Residuen-Minimierung unter Verwendung der lp-Norm, einschließ lich des nicht-konvexen und nicht-stetigen Falles von $p<1$. Im Zentrum der Arbeit stehen sowohl die theoretische Analyse des Problems als auch dessen praktische Anwendung. Die gewonnen experimentellen Erkenntnisse zeigen die überlegenheit der vorgestellten Methodik gegenüber aktuellen Vergleichsverfahren.

Zunächst werden zwei iterative Algorithmen zur Low-Rank Approximation einer einzelnen Matrix konzipiert. Die sogenannte iteratively reweighted singular value decomposition (IR-SVD) Methode basiert auf einer Matrix-Singulärwertzerlegung, bei der die zugrundeliegende Matrix in jeder Iteration des Verfahrens neu gewichtet wird. In der zweiten Methode wird das nicht-konvexe lp-Matrixfaktorisierungsproblem durch eine Reihe einfacherer lp-Minimierungsprobleme ersetzt, wobei die auftretenden Vektoren als eigenständige Variablen betrachtet werden. Zu beiden Verfahren werden Anwendungsbeispiele aus verschiedenen Bereichen diskutiert, darunter die Separation von Bildkomponenten, die Vordergrunddetektion in der Videoüberwachung, Beispiele aus dem Bereich Array-Signalverarbeitung, sowie die Richtungsschätzung zur Quellenlokalisierung in impulsivem Rauschen.

Anschließ end wird die Low-Rank Approximation mit fehlenden Werten (engl. robust matrix completion) behandelt, für welche ebenfalls zwei Verfahren vorgestellt werden. Das erste Verfahren bietet einen iterativen Lösungsansatz, welcher auf der Berechnung linearer l_p-Regressionsproblemen basiert. Das zweite Verfahren beruht auf der sogenannten alternating direction method of multipliers (ADMM) im l_p-Raum. Bei jeder Iteration von ADMM wird eine Matrixfaktorisierung im Sinne der kleinsten Fehlerquadrate (engl. least squares, LS) durchgeführt, wofür ein Näherungsoperator basierend auf der $p$-ten Potenz der lp-Norm berechnet wird. Die LS-Faktorisierung wird effizient durch lineare Regression gelöst, wobei der Nährerungsoperator über die Nullstellen einer skalaren nichtlinearen Funktion berechnet wird. Beide Algorithmen sind in der Problemgröß e skalierbar. Die Verfahren werden anhand von Beispielen zur kollaborativen Filterung, der automatischen Bildvervollständigung, sowie anhand einer Anwendung im Bereich Empfehlungssysteme demonstriert.

Für die robuste Low-Rank Approximation mehrerer Matrizen (RLRAMM) mit Ausreiß ern werden lp-greedy pursuit (lp-GP) Algorithmen konzipiert. Das lp-GP Verfahren mit $0