Background: Principal-Component Analysis (PCA) is a cornerstone method in data analysis, machine learning, and signal processing, with applications in computer vision, neuroscience, robotics, and medicine, to name a few. PCA is often used for dimensionality reduction, noise removal, compression, classification, clustering, and feature extraction. Considering a collection of vector-measurements arranged as columns of a matrix, PCA seeks a low-dimensional subspace (column-wise orthonormal matrix) such that, when the processed data matrix is projected on said subspace, the Euclidean distance (Frobenius norm) of the projected data from the original processed matrix is minimized. By the projection theorem, PCA can equivalently be formulated as a projection-maximization problem. That is, PCA equivalently seeks a column-wise orthonormal matrix such that the Frobenius norm of its product with the processed data matrix is maximized. 

Motivation: Despite its success, scholars have long observed that PCA exhibits strong sensitivity against outliers—i.e., vector-measurements that lie far away from the nominal ones. Outliers often appear in modern datasets as a small fraction of the data due to: errors in data storage/transfer, sensor malfunctions, and even deliberate data contamination in adversarial environments. The outlier sensitivity of PCA is often attributed to its Euclidean/Frobenius norm formulation which places squared emphasis on each measurement benefiting outliers. Accordingly, applications that rely on PCA may attain compromised performance when outliers appear in the processed matrix. To remedy the impact of outliers, many alternatives have been proposed. For instance, a line of research suggests to model the processed matrix as the sum of a low-rank matrix (signal-of-interest carrying) and another matrix modeling sparse outliers. A more straightforward approach considers the projection-maximization formulation of standard PCA and substitutes the outlier-responsive Frobenius norm by the more robust L1-norm which places linear emphasis on each measurement effectively suppressing outliers. 

Contributions: In this line of research, we consider the projection-maximization formulation of standard PCA and replace the Frobenius norm by the Lp-norm, specifically, for p<1. Effectively, we consider a PCA formulation that places sub-linear emphasis on each measurement the importance of which can be tuned by the value of p. Despite previous attempts, the solution to Lp-norm PCA (Lp-PCA) remains unknown. In this project we show, for the first time, that Lp-PCA can be solved exactly via combinatorial optimization. That is, we show that the original problem can, without loss of generality, be divided into a finite number (which depends on the number of columns in the processed matrix) of smaller problems each of which is a convex problem and therefore admits an exact solution. Accordingly, an exhaustive search across all subproblems will return the exact solution to Lp-PCA. Moreover, we explore and develop more intelligent algorithms that can compute the exact solution with significantly lower computational cost than that of the exhaustive search. We also develop efficient approximate solvers of low-cost. Numerical studies on matrix reconstruction and classification of medical data corroborate the merits of Lp-PCA.

• [C15] D. G. Chachlakis and P. P. Markopoulos, Novel Algorithms for Lp-quasi-norm Principal-Component Analysis, in Proceedings European Signal Processing Conference (EUSIPCO 2020), Amsterdam, NL, January 2021.
  IEEEXplore, Python Codes

• [C12] D. G. Chachlakis and P. P. Markopoulos, Combinatorial search for the Lp-norm principal component of a matrix, in Proceedings IEEE Asilomar Conference on Signals, Systems, and Computers (IEEE ACSSC 2019), Pacific Grove, CA, November 2019.
  IEEE Xplore, Python Codes

• Assist. Professor Panos P. Markopoulos, Dept. of Electrical and Microelectronic Engineering, Rochester Institute of Technology.