Fast subspace approximation via greedy least-squares

DOI10.1007/S00365-014-9273-ZMaRDI QIDQ745854zbMATH OpenOpenAlexFDO

Authors Felix Krahmer, M. A. Iwen

Publication date 14 October 2015

Published in Constructive Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1413

zbMATH Keywords

dimensionality reductionleast-squaresapproximation algorithmsgreedy algorithms\(n\)-widthssubspace approximation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms for approximation of functions (65D15) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Abstract: In this note, we develop fast and deterministic dimensionality reduction techniques for a family of subspace approximation problems. Let $Psubsetmathbbm{R}^N$ be a given set of $M$ points. The techniques developed herein find an $O(nlogM)$-dimensional subspace that is guaranteed to always contain a near-best fit $n$-dimensional hyperplane $mathcalH$ for $P$ with respect to the cumulative projection error $$, for any chosen $p>2$. The deterministic algorithm runs in $ildeO(M{N}^2)$-time, and can be randomized to run in only $ildeO(MNn)$-time while maintaining its error guarantees with high probability. In the case $p=infty$ 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 $el{l}_2$-distance to any point in the convex hull of $P$ is minimized. The resulting algorithm remains $ildeO(MNn)$-time. In addition, the dimensionality reduction techniques developed herein can also be combined with other existing subspace approximation algorithms for $2<pleqinfty$ - including more accurate algorithms based on convex programming relaxations - in order to reduce their runtimes.

Recommendations

• Efficient subspace approximation algorithms
• A greedy algorithm for subspace approximation problem
• Coresets and sketches for high dimensional subspace approximation problems
• Algorithms and hardness for subspace approximation
• Sampling-based dimension reduction for subspace approximation with outliers

Cites work

• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• A unified framework for approximating and clustering data
• Algorithms and hardness for subspace approximation
• An improved algorithm for approximating the radii of point sets
• Approximating the Radii of Point Sets
• Efficient subspace approximation algorithms
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Kolmogorov's heritage in mathematics. Transl. from the French
• Minimum-volume enclosing ellipsoids and core sets
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Projective clustering in high dimensions using core-sets
• Robust computation of linear models by convex relaxation
• Rounding of Polytopes in the Real Number Model of Computation
• Sampling-based dimension reduction for subspace approximation
• The Matrix Eigenvalue Problem
• Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse

Cited in

(10)

• Efficient point-to-subspace query in \(\ell^1\) with application to robust object instance recognition
• On greedy algorithm approximating Kolmogorov widths in Banach spaces
• Speeding up the GVW algorithm via a substituting method
• A greedy algorithm for subspace approximation problem
• On recovery guarantees for one-bit compressed sensing on manifolds
• Efficient subspace approximation algorithms
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• An accelerated subspace iteration method
• A dimension reduction scheme for the computation of optimal unions of subspaces
• Efficient subspace approximation algorithms

This page was built for publication: Fast subspace approximation via greedy least-squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q745854)