# Optimal Algorithms for L1-subspace Signal Processing

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2014.

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

- [Fun with Flags: Robust Principal Directions via Flag Manifolds](https://mlsanity.com/paper/2401.04071/) (2024)
- [Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysis](https://mlsanity.com/paper/2402.09754/) (2024)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Robust Principal Component Analysis Using a Novel Kernel Related with the L1-Norm](https://mlsanity.com/paper/2105.11634/) (2021)
- [Multiplication-Avoiding Variant of Power Iteration with Applications](https://mlsanity.com/paper/2110.12065/) (2021)
- [l1-norm regularized l1-norm best-fit lines](https://mlsanity.com/paper/2402.16712/) (2024)
- [Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search](https://mlsanity.com/paper/2106.12190/) (2021)
- [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)
- [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)
- [Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data](https://mlsanity.com/paper/2603.29715/) (2026)
- [Mean-Shift PCA by Knockoff Mean](https://mlsanity.com/paper/2605.25460/) (2026)
- [Conditioned free-energy density of proteins using unbalanced solutions to constraint satisfaction problems](https://mlsanity.com/paper/2606.01329/) (2026)

## Abstract (arXiv)

We describe ways to define and calculate L1-norm signal subspaces which are less sensitive to outlying data than L2-calculated subspaces. We start with the computation of the L1 maximum-projection principal component of a data matrix containing N signal samples of dimension D. We show that while the general problem is formally NP-hard in asymptotically large N, D, the case of engineering interest of fixed dimension D and asymptotically large sample size N is not. In particular, for the case where the sample size is less than the fixed dimension (N<D), we present in explicit form an optimal algorithm of computational cost 2N. For the case N ≥ D, we present an optimal algorithm of complexity mathcal O(ND). We generalize to multiple L1-max-projection components and present an explicit optimal L1 subspace calculation algorithm of complexity mathcal O(NDK-K+1) where K is the desired number of L1 principal components (subspace rank). We conclude with illustrations of L1-subspace signal processing in the fields of data dimensionality reduction, direction-of-arrival estimation, and image conditioning/restoration.