# l1-norm regularized l1-norm best-fit lines

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 23 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 2 of 2)

- [Optimal Algorithms for L1-subspace Signal Processing](https://mlsanity.com/paper/1405.6785/) (2014)
- [On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation](https://mlsanity.com/paper/1509.09236/) (2015)

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

- [Robust conditional dimension reduction for dissimilarity data](https://mlsanity.com/paper/2609.06284/) (2026)

## Abstract (arXiv)

In this work, we propose an optimization framework for estimating a sparse robust one-dimensional subspace. Our objective is to minimize both the representation error and the penalty, in terms of the l1-norm criterion. Given that the problem is NP-hard, we introduce a linear relaxation-based approach. Additionally, we present a novel fitting procedure, utilizing simple ratios and sorting techniques. The proposed algorithm demonstrates a worst-case time complexity of O(n2 m log n) and, in certain instances, achieves global optimality for the sparse robust subspace, thereby exhibiting polynomial time efficiency. Compared to extant methodologies, the proposed algorithm finds the subspace with the lowest discordance, offering a smoother trade-off between sparsity and fit. Its architecture affords scalability, evidenced by a 16-fold improvement in computational speeds for matrices of 2000x2000 over CPU version. Furthermore, this method is distinguished by several advantages, including its independence from initialization and deterministic and replicable procedures. Furthermore, this method is distinguished by several advantages, including its independence from initialization and deterministic and replicable procedures. The real-world example demonstrates the effectiveness of algorithm in achieving meaningful sparsity, underscoring its precise and useful application across various domains.