Optimal algorithms for L1-norm Principal Component Analysis: New tools for signal processing and machine learning with few and/or faulty training data
MetadataShow full item record
The objective of this work is the development of a solid theoretical and algorithmic framework for outlier-resistant L 1 -norm Principal Component Analysis (PCA). PCA is the statistical data analysis technique that has been, for over a century, the "mainstay" of modern signal processing and machine learning, with numerous important applications in wireless communications, computer networks, computer vision, image processing, and bio-informatics, to name a few. However, researchers have long observed that standard L 2 -norm-based PCA is highly responsive to corrupted, highly deviating, irregular data-points (outliers) in the data, even when they appear in a vanishingly small numbers. Because of the frequent appearance of such outliers in real-world applications and the sensitivity of L 2 -norm Principal Components (PCs), a great amount of research effort has been placed in the past few decades on calculating and using instead PCs that define L 1 -norm maximum-projection data subspaces ( L 1 -PCA). A summary of our contributions in this manuscript follows. In Chapter 1, we translate L 1 -PCA into combinatorial optimization and deliver the first two optimal algorithms in the literature for its exact calculation. In Chapter 2, we propose a third, efficient L 1 -PCA algorithm (complexity close to that of standard L 2 -PCA) that attains optimal performance with empirical probability close to 1, outperforming on average all counterparts of comparable computational cost existing in the literature. This algorithm was designed to bridge the gap between our optimal algorithms of high computational cost and the existing low-cost suboptimal algorithms of high performance degradation and, thus, be the method of choice for real-world L 1 -PCA of large data. In Chapter 3, we focus on the special case of real, non-negative matrices (e.g., images, graph adjacency matrices) and calculate their optimal L 1 -PC with linear cost. Then, we present a novel L 1 -PCA-based technique for the recovery of an image from a set of few, possibly severely corrupted copies. In Chapter 4, we employ our L 1 -PCA tools from Chapters 1 and 2 for developing a state-of-the-art subspace-based direction-of-arrival (DoA) estimation method, that is capable of attaining performance similar to that of the highly popular L 2 -subspace methods in nominal system operation, while exhibiting inherent resistance against unknown data record contamination. In Chapter 5, we steer our focus from real to complex data analysis and define, for the first time, the L 1 -PC of complex data. Then, we present an algorithm for calculating the L 1 -PC of a complex data matrix and use it to devise a novel outlier-resistant subspace-based DoA estimation method. Finally, in Chapter 6, we establish the MMSE operation for Pseudonoise (PN) masked data in the form of a time varying linear filter, suggest an implementation that avoids repeated input autocorrelation matrix inversion, and develop an auxiliary-vector (AV) MMSE filter estimator with state-of-the-art short-data-record estimation performance.