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.