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

摘要

Given an integer k≥1 and a set P of n points in ℝ^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 (ℓ_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 z∉1,2, e.g., z=∞, and handling outliers/sparsity. Open code and experimental results on real-world datasets are also provided.