# k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 64 references that are in the map.
- First posted on arXiv 19 Jul 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Optimal Algorithms for L1-subspace Signal Processing](https://mlsanity.com/paper/1405.6785/) (2014)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Tight Sensitivity Bounds For Smaller Coresets](https://mlsanity.com/paper/1907.01433/) (2019)
- [Efficient L1-Norm Principal-Component Analysis via Bit Flipping](https://mlsanity.com/paper/1610.01959/) (2016)
- [Dimensionality Reduction for Sum-of-Distances Metric](https://mlsanity.com/paper/1912.12003/) (2019)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings](https://mlsanity.com/paper/2202.09797/) (2022)
- [Self-localization from Images with Small Overlap](https://mlsanity.com/paper/1603.00993/) (2016)
- [Some Options for L1-Subspace Signal Processing](https://mlsanity.com/paper/1309.1194/) (2013)
- [Low Rank Matrix Approximation in Linear Time](https://mlsanity.com/paper/1410.8802/) (2014)
- [Smart-Inspect: Micro Scale Localization and Classification of Smartphone Glass Defects for Industrial Automation](https://mlsanity.com/paper/2010.00741/) (2020)

## Abstract (arXiv)

Given an integer k≥1 and a set P of n points in REALd, the classic k-PCA (Principle Component Analysis) approximates the affine k-subspace mean of P, which is the k-dimensional affine linear subspace that minimizes its sum of squared Euclidean distances (ℓ2,2-norm) over the points of P, i.e., the mean of these distances. The k-subspace median is the subspace that minimizes its sum of (non-squared) Euclidean distances (ℓ2,1-mixed norm), i.e., their median. The median subspace is usually more sparse and robust to noise/outliers than the mean, but also much harder to approximate since, unlike the ℓz,z (non-mixed) norms, it is non-convex for k<d-1. We provide the first polynomial-time deterministic algorithm whose both running time and approximation factor are not exponential in k. More precisely, the multiplicative approximation factor is √d, and the running time is polynomial in the size of the input. We expect that our technique would be useful for many other related problems, such as ℓ2,z norm of distances for znot ∈ br1,2, e.g., z=∞, and handling outliers/sparsity. Open code and experimental results on real-world datasets are also provided.