k-PCA for (non-squared) Euclidean Distances: Deterministic Polynomial Time Approximation
Abstract
Given an integer $k\geq1$ and a set $P$ of $n$ points in $\mathbb{R}^d$, the classic $k$-PCA (Principal 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 ($\ell_{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 ($\ell_{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 $\ell_{z,z}$ (non-mixed) norms, it is non-convex for $k Cite this Paper BibTeX @InProceedings{pmlr-v300-greenhut26a, title = { $k$-PCA for (non-squared) Euclidean Distances: Deterministic Polynomial Time Approximation }, author = {Greenhut, Daniel and Feldman, Dan}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {739--747}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/greenhut26a/greenhut26a.pdf}, url = {https://proceedings.mlr.press/v300/greenhut26a.html}, abstract = { Given an integer $k\geq1$ and a set $P$ of $n$ points in $\mathbbR^d$, the classic $k$-PCA (Principal 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 ($\ell_{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 ($\ell_{2,1}$-mixed norm), i.e., their median. The median subspace is usually more sparse and r