Guessing efficiently for constrained subspace approximation

DOI10.4230/LIPICS.ICALP.2025.29MaRDI QIDQ7346460zbMATH OpenFDO

Authors Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian, David P. Woodruff

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.29

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A new coreset framework for clustering
• A PTAS for ℓ_p-Low Rank Approximation
• A PTAS for k-means clustering based on weak coresets
• Algorithms and hardness for subspace approximation
• An almost optimal algorithm for computing nonnegative rank
• An improved approximation algorithm for the column subset selection problem
• Bypassing UGC from some optimal geometric inapproximability results
• Clustering large graphs via the singular value decomposition
• Column subset selection via sparse approximation of SVD
• Dimensionality reduction for k-means clustering and low rank approximation
• Efficient volume sampling for row/column subset selection
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 6438182 (Why is no real title available?)
• Input sparsity and hardness for robust subspace approximation
• Near-optimal column-based matrix reconstruction
• Numerical linear algebra in the streaming model
• Optimal column-based low-rank matrix reconstruction
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Sparse PCA on fixed-rank matrices
• Truncated power method for sparse eigenvalue problems
• Weighted low rank approximations with provable guarantees

This page was built for publication: Guessing efficiently for constrained subspace approximation

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