A greedy algorithm for subspace approximation problem

DOI10.4230/LIPICS.SWAT.2018.30MaRDI QIDQ5116494zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmssubspace approximation

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(5)

• A Bidirectional Greedy Heuristic for the Subspace Selection Problem
• 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

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)