# Efficient L1-Norm Principal-Component Analysis via Bit Flipping

arXiv: https://arxiv.org/abs/1610.01959 · HTML: https://mlsanity.com/paper/1610.01959/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2016.

## Built on by (most cited first, 9 of 9)

- [Fun with Flags: Robust Principal Directions via Flag Manifolds](https://mlsanity.com/paper/2401.04071/) (2024)
- [Multiplication-Avoiding Variant of Power Iteration with Applications](https://mlsanity.com/paper/2110.12065/) (2021)
- [Distance Based Image Classification: A solution to generative classification's conundrum?](https://mlsanity.com/paper/2210.01349/) (2022)
- [Robust Singular Values based on L1-norm PCA](https://mlsanity.com/paper/2210.12097/) (2022)
- [On Finite-Step Convergence of the Non-Greedy Algorithm and Proximal Alternating Minimization Method with Extrapolation for L1-Norm PCA](https://mlsanity.com/paper/2302.07712/) (2023)
- [Predictability of Machine Learning Algorithms and Related Feature Extraction Techniques](https://mlsanity.com/paper/2305.00449/) (2023)
- [Quantum Annealing for Robust Principal Component Analysis](https://mlsanity.com/paper/2501.10431/) (2025)
- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)
- [Mean-Shift PCA by Knockoff Mean](https://mlsanity.com/paper/2605.25460/) (2026)

## Abstract (arXiv)

It was shown recently that the K L1-norm principal components (L1-PCs) of a real-valued data matrix mathbf X ∈ mathbb RD × N (N data samples of D dimensions) can be exactly calculated with cost O(2NK) or, when advantageous, O(NdK - K + 1) where d=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 + N2(K4 + dK2) + dNK3), 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.