A greedy algorithm for subspace approximation problem

DOI10.4230/LIPICS.SWAT.2018.30zbMATH Open1477.68494OpenAlexW2806431894MaRDI QIDQ5116494FDOQ5116494

Authors: Nguyen Kim Thang 

Publication date: 25 August 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/swat/swat2018.html#Thang18

Recommendations

• Algorithms and hardness for subspace approximation
• Efficient subspace approximation algorithms
• Fast subspace approximation via greedy least-squares
• Coresets and sketches for high dimensional subspace approximation problems
• Sampling-based dimension reduction for subspace approximation with outliers

zbMATH Keywords

approximation algorithmssubspace approximation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Sampling algorithms for \(l_2\) regression and applications
• Sampling Algorithms and Coresets for $\ell_p$ Regression
• On maximization of quadratic form over intersection of ellipsoids with common center
• Approximating the Radii of Point Sets
• Subgradient and sampling algorithms for \(\ell_1\) regression
• Algorithms and hardness for subspace approximation
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Bypassing UGC from some optimal geometric inapproximability results

Cited In (5)

• Speeding up the GVW algorithm via a substituting method
• Fast subspace approximation via greedy least-squares
• Algorithms and hardness for subspace approximation
• Efficient subspace approximation algorithms
• A Bidirectional Greedy Heuristic for the Subspace Selection Problem

This page was built for publication: A greedy algorithm for subspace approximation problem

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