TU Darmstadt / ULB / TUprints

Robust Low-Rank Approximation of Matrices in lp-Space

Zeng, Wenjun (2018)
Robust Low-Rank Approximation of Matrices in lp-Space.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PhD thesis of Wenjun Zeng - Text
2018-07-05_Zeng_Wenjun.pdf - Accepted Version
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (6MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Robust Low-Rank Approximation of Matrices in lp-Space
Language: English
Referees: Zoubir, Prof. Dr. Abdelhak ; So, Prof. Dr. Hing Cheung
Date: 8 July 2018
Place of Publication: Darmstadt
Date of oral examination: 5 July 2018
Abstract:

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<p<2$ solves the RLRAMM by decomposing it into a series of rank-one approximations. At each iteration, it finds the best rank-one approximation by minimizing the $\ell_p$-norm of the residual and then, the rank-one basis matrices are subtracted from the residual. A successive minimization approach is designed for the $\ell_p$-rank-one fitting. Only weighted medians are required to compute for solving the most attractive case with $p=1$, yielding that the complexity is near-linear with the number and dimension of the matrices. Thus, the $\ell_1$-GP is near-scalable to large-scale problems. The convergence of the $\ell_p$-GP is theoretically proved. In particular, the sum of the $\ell_p$-norms of the residuals decays exponentially. We reveal that the worst-case bound of the convergence rate is related to the $\ell_p$-correlation of the residual and the current solution. The $\ell_p$-GP has a higher compression ratio than the existing methods. For the special case of $p=2$, the orthogonal greedy pursuit (OGP) is further developed to accelerate the convergence, where the cost of weight re-computation is reduced by a recursive update manner. Tighter and more accurate bounds of the convergence rates are theoretically derived for $p=2$. Applications to data compression, robust image reconstruction and computer vision are provided.

Alternative Abstract:
Alternative AbstractLanguage

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<p<2$ löst die RLRAMM Problematik, indem das Kernproblem in eine Reihe von Rang-Eins Approximationsproblemen zerlegt wird. Bei jeder Iteration des Verfahrens wird die beste Rang-Eins Approximation durch Minimierung der l_p-Norm des Residuums gefunden, woraufhin die Rang-Eins Basismatrizen vom Residuum subtrahiert werden. Anschließ end wird ein Minimierungsansatz zur l_p-Rang-Eins Berechnung vorgestellt. Da der Sonderfall $p=1$ nur die Berechnung gewichteter Mediane erfordert, ist die Komplexität des Verfahrens beinahe linear in der Anzahl und Dimension der Matrizen, wodurch l1-GP nahezu skalierbar für groß e Probleme wird. Die Konvergenz von l_p-GP wird formal nachgewiesen, wobei gezeigt wird, dass die Summe der lp-Normen der Residuen exponentiell abklingt. Hierbei wird ein Zusammenhang zwischen der Konvergenzrate im ungünstigsten Fall und der lp-Korrelation zwischen den Residuen und der aktuellen Lösung hergestellt. Des Weiteren wird gezeigt, dass lp-GP ein höheres Kompressionsverhältnis gegenüber bisherigen Methoden aufweist. Für den Spezialfall $p=2$ wird die orthogonal greedy pursuit (OGP) Methode weiterentwickelt, um deren Konvergenz zu beschleunigen. Gleichzeitig wird der Berechnungsaufwand der erforderlichen Neugewichtung durch ein rekursives Updateverfahren reduziert. Abschließ end werden festere und genauere Grenzen der Konvergenzraten für den Fall $p=2$ abgeleitet und Anwendungen zur Datenkompression, zur robusten Bildrekonstruktion und zur Bildverarbeitung diskutiert.

German
URN: urn:nbn:de:tuda-tuprints-75642
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Signal Processing
Date Deposited: 20 Jul 2018 08:09
Last Modified: 09 Jul 2020 02:09
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/7564
PPN: 433871040
Export:
Actions (login required)
View Item View Item