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

Daniel Greenhut, Dan Feldman
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:739-747, 2026.

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 \emph{$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 \emph{$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 $\mathbb{R}^d$, the classic $k$-PCA (Principal Component Analysis) approximates the affine \emph{$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 \emph{$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
Endnote
%0 Conference Paper %T $k$-PCA for (non-squared) Euclidean Distances: Deterministic Polynomial Time Approximation %A Daniel Greenhut %A Dan Feldman %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-greenhut26a %I PMLR %P 739--747 %U https://proceedings.mlr.press/v300/greenhut26a.html %V 300 %X 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 \emph{$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 \emph{$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
APA
Greenhut, D. & Feldman, D.. (2026). $k$-PCA for (non-squared) Euclidean Distances: Deterministic Polynomial Time Approximation . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:739-747 Available from https://proceedings.mlr.press/v300/greenhut26a.html.

Related Material