2013/12/05 by Mark Iwen, Iwen, Mark, Felix Krahmer +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1312.1413
openalex publication_date 2013/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. Let P⊂ \mathbbmRN be a given set of M points. The techniques developed herein find an O(n log M)-dimensional subspace that is guaranteed to always contain a near-best fit n-dimensional hyperplane H for P with respect to the cumulative projection error (∑_\bf x ∈ P ‖ \bf x - ΠH \bf x ‖p2)1/p, for any chosen p > 2. The deterministic algorithm runs in O (MN2)-time, and can be randomized to run in only O (MNn)-time while maintaining its error guarantees with high probability. In the case p = ∞ the dimensionality reduction techniques can be combined with efficient algorithms for computing the John ellipsoid of a data set in order to produce an n-dimensional subspace whose maximum ℓ2-distance to any point in the convex hull of P is minimized. The resulting algorithm remains O (MNn)-time. In addition, the dimensionality reduction techniques developed herein can also be combined with other existing subspace approximation algorithms for 2 < p ≤ ∞ - including more accurate algorithms based on convex programming relaxations - in order to reduce their runtimes.