Efficient L1-Norm Principal-Component Analysis via Bit Flipping

Abstract

It was shown recently that the $K$ L1-norm principal components (L1-PCs) of a real-valued data matrix $\mathbf{X}\in {\mathbb{R}}^{D\times N}$ ($N$ data samples of $D$ dimensions) can be exactly calculated with cost $\mathcal{O}(2^{NK})$ or, when advantageous, $\mathcal{O}(N^{dK-K+1})$ where $d=\mathrm{rank}(\mathbf{X})$, $K<d$ [1],[2]. In applications where $\mathbf{X}$ is large (e.g., "big" data of large $N$ and/or "heavy" data of large $d$), these costs are prohibitive. In this work, we present a novel suboptimal algorithm for the calculation of the $K<d$ L1-PCs of $\mathbf{X}$ of cost $\mathcal{O}(ND\min \{N,D\}+N^2(K^4+d{K}^2)+dN{K}^3)$, which is comparable to that of standard (L2-norm) PC analysis. Our theoretical and experimental studies show that the proposed algorithm calculates the exact optimal L1-PCs with high frequency and achieves higher value in the L1-PC optimization metric than any known alternative algorithm of comparable computational cost. The superiority of the calculated L1-PCs over standard L2-PCs (singular vectors) in characterizing potentially faulty data/measurements is demonstrated with experiments on data dimensionality reduction and disease diagnosis from genomic data.

References in corpus (1)

• Optimal Algorithms for $L_1$-subspace Signal Processing

Cited by in corpus (9)

• L1-norm Principal-Component Analysis of Complex Data
• A Nonsmooth Dynamical Systems Perspective on Accelerated Extensions of ADMM
• The Exact Solution to Rank-1 L1-norm TUCKER2 Decomposition
• A robust principal component analysis for outlier identification in messy microcalorimeter data
• Optimization for L1-Norm Error Fitting via Data Aggregation
• Self-Paced Probabilistic Principal Component Analysis for Data with Outliers
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• A Rank Revealing Factorization Using Arbitrary Norms
• Optimal ${\ell }_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation