Algorithms and hardness for subspace approximation

MaRDI QIDQ5365058zbMATH OpenFDO

Authors Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133075

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• A greedy algorithm for subspace approximation problem
• Efficient subspace approximation algorithms
• scientific article; zbMATH DE number 7053310
• Bypassing UGC from some optimal geometric inapproximability results
• Sampling-based dimension reduction for subspace approximation with outliers

Cited in

(15)

• Sampling-based dimension reduction for subspace approximation with outliers
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Bypassing UGC from some optimal geometric inapproximability results
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• On computing centroids according to the p-norms of Hamming distance vectors
• A greedy algorithm for subspace approximation problem
• On approximating matrix norms in data streams
• Clustering affine subspaces: hardness and algorithms
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• New subset selection algorithms for low rank approximation: offline and online
• Efficient subspace approximation algorithms
• Turning big data into tiny data: coresets for unsupervised learning problems
• Guessing efficiently for constrained subspace approximation
• Fast subspace approximation via greedy least-squares

This page was built for publication: Algorithms and hardness for subspace approximation

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