# Some Options for L1-Subspace Signal Processing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2013.

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

- [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)

## 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 focus on the computation of the L1 maximum-projection principal component of a data matrix containing N signal samples of dimension D and conclude that the general problem is formally NP-hard in asymptotically large N, D. We prove, however, that the case of engineering interest of fixed dimension D and asymptotically large sample support N is not and we present an optimal algorithm of complexity O(ND). We generalize to multiple L1-max-projection components and present an explicit optimal L1 subspace calculation algorithm in the form of matrix nuclear-norm evaluations. We conclude with illustrations of L1-subspace signal processing in the fields of data dimensionality reduction and direction-of-arrival estimation.