Decentralized Singular Value Decomposition of Symmetric and non-Symmetric Matrices for Large-scale Sensor Networks

The Eigenvalue Decomposition (EVD) and the Singular Value Decomposition (SVD) are fundamental matrix factorization techniques that play crucial roles in various application areas such as signal processing, data mining, and machine learning. Efficient and numerically stable implementations of the EVD and SVD have been long-established research topics of interest, e.g., in sensor array processing. As the number of measurements increases drastically nowadays, the conventional approaches that collect all sample measurements in a fusion center to perform the EVD and SVD often become impractical or even impossible. To this end, scalable solutions are preferred, such as the decentralized approaches that involves only peer-to-peer communication and utilize local computation and storage resources.

In this thesis, we first propose a communication efficient decentralized EVD algorithm that addresses the EVD as the sum of the rank-one components. The proposed algorithm utilizes a local lightweight rational function approximation approach and parallel averaging consensus algorithms to estimate and track the eigenvalues and eigenvectors in a fully decentralized online manner. To further reduce the overall communication cost and local computational overhead, e.g., in applications of Principal Component Analysis, a novel and non-trivial truncation technique is proposed. Based on the proposed decentralized EVD algorithm, two types of important application examples are examined: the online EVD of a sample covariance matrix over the network with the application in decentralized Direction-of-Arrival estimation and tracking, and the online computation of the spectra of the graph Laplacian matrix that is important, e.g., in Graph Fourier Analysis and graph dependent filter design.

Second, we extend the proposed decentralized EVD algorithm to non-symmetric/non-Hermitian matrices to perform the decentralized SVD. Based on the availability of the matrix under consideration, two scenarios of the decentralized SVD are examined. While in the first scenario, the matrix of interest is row-wisely available in each local node in the network, in the second scenario, the matrix of interest implicitly forms an outer product generated from two different series of measurements. Combining the lightweight local rational function approximation approach and parallel averaging consensus algorithms, two decentralized implementations of the SVD are proposed to cope with the two aforementioned scenarios. In addition, two respective application examples in extremely large-scale sensor array systems are examined with the proposed decentralized SVD algorithms, i.e., the decentralized sensor localization via low-rank matrix completion for the first scenario and the decentralized passive radar detection for the second scenario.

All simulation results show that our proposed decentralized EVD and decentralized SVD algorithms benefit from the rank-one expressions and thus admit low overall communication cost compared with the state-of-the-art decentralized power method. By employing the truncation technique, both communication costs and local computational overhead are significantly reduced, while a performance comparable to that of the centralized approach is achieved, when principal components are present and of interest.

Die Eigenwertzerlegung (englisch: Eigenvalue Decomposition, kurz EVD) und die Singulärwertzerlegung (englisch: Singular Value Decomposition, kurz SVD) sind fundamentale Matrixfaktorisierungstechniken, die in verschiedenen Anwendungsbereichen wie Signalverarbeitung, Data Mining, und maschinelles Learnen eine entscheidende Rolle spielen. Effiziente und numerisch stabile Implementierungen von EVD und SVD sind seit langem wichtige Forschungsthemen, beispielsweise in der Sensorgruppensignalverarbeitung. Da die Anzahl der Messungen heutzutage drastisch ansteigt, sind konventionelle Ansätze, die alle Messproben in einem Fusionszentrum sammeln, um die EVD und SVD durchzuführen, zunehmend als unpraktisch oder sogar unmöglich. Daher werden skalierbare Lösungen bevorzugt, wie dezentrale Ansätze, die nur Peer-to-Peer-Kommunikation beinhalten und lokale Rechen- und Speicherressourcen nutzen.

In dieser Arbeit schlagen wir zunächst einen kommunikationseffizienten dezentralen EVD-Algorithmus vor, der die EVD als Summe von Rang-Eins-Komponenten behandelt. Der vorgeschlagene Algorithmus verwendet einen lokalen, leichtgewichtigen rationalen Funktionsapproximationsansatz und parallele Mittelungskonsensalgorithmen, um die Eigenwerte und Eigenvektoren vollständig dezentral online zu schätzen und zu verfolgen. Um die Gesamtkommunikationskosten und den lokalen Rechenaufwand weiter zu reduzieren, zum Beispiel in Anwendungen der Hauptkomponentenanalyse, wird eine neuartige und nicht-triviale Trunkierungstechnik vorgeschlagen. Basierend auf den vorgeschlagenen dezentralen EVD-Algorithmen werden zwei wichtige Anwendungsbeispiele untersucht: die Online-EVD einer Stichprobenkovarianzmatrix über das Netzwerk mit Anwendung in dezentralen Richtungsschätzung und Verfolgung sowie die Online-Berechnung der Spektren der Graph-Laplace-Matrix, die beispielsweise in der Graph-Fourier-Analyse und dem graphabhängigen Filterentwurf wichtig ist.

Zweitens erweitern wir den vorgeschlagenen dezentralen EVD-Algorithmus auf nicht-symmetrische/nicht-hermitesche Matrizen, um die dezentrale SVD durchzuführen. Basierend auf der Verfügbarkeit der betrachteten Matrix werden zwei Szenarien der dezentralen SVD untersucht. Während im ersten Szenario die betrachtete Matrix zeilenweise in jedem lokalen Knoten im Netzwerk verfügbar ist, bildet sie im zweiten Szenario implizit ein äußeres Produkt, das aus zwei verschiedenen Messreihen generiert wird. Durch die Kombination des leichtgewichtigen, lokalen rationalen Funktionsapproximationsansatzes und der parallelen Mittelungskonsensalgorithmen werden zwei dezentrale Implementierungen der SVD vorgeschlagen, um die beiden genannten Szenarien zu bewältigen. Darüber hinaus, zwei entsprechende Anwendungsbeispiele in besonders großen Sensorgruppensystemen werden mit den vorgeschlagenen dezentralen SVD-Algorithmen untersucht: die dezentrale Sensorlokalisierung durch Niedrigrang-Matrixvervollständigung für das erste Szenario und die dezentrale passive Radardetektion für das zweite Szenario.

Alle Simulationsergebnisse zeigen, dass unsere vorgeschlagenen dezentralen EVD- und SVD-Algorithmen von den Rang-Eins-Ausdrücken profitieren und somit im Vergleich zur State-of-the-Art, dezentrale Power-Methode niedrige Gesamtkommunikationskosten aufweisen. Durch den Einsatz der Trunkierungstechnik werden sowohl die Kommunikationskosten als auch der lokale Rechenaufwand erheblich reduziert, während eine Leistung vergleichbar mit der des zentralen Ansatzes erreicht wird, wenn Hauptkomponenten vorhanden und von Interesse sind.