Fast subspace approximation via greedy least-squares

DOI10.1007/s00365-014-9273-zzbMath1406.65012arXiv1312.1413OpenAlexW1984578222MaRDI QIDQ745854

Felix Krahmer, Mark 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

least-squaresapproximation algorithmsgreedy algorithmsdimensionality reduction\(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)

Related Items

On greedy algorithm approximating Kolmogorov widths in Banach spaces, On recovery guarantees for one-bit compressed sensing on manifolds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Minimum-volume enclosing ellipsoids and core sets
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• Robust computation of linear models by convex relaxation
• On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
• Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse
• Sampling-based dimension reduction for subspace approximation
• Projective clustering in high dimensions using core-sets
• Rounding of Polytopes in the Real Number Model of Computation
• A unified framework for approximating and clustering data
• Approximating the Radii of Point Sets
• The Matrix Eigenvalue Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques