Near Optimal Column-Based Matrix Reconstruction

DOI10.1109/FOCS.2011.21MaRDI QIDQ5495020zbMATH OpenFDO

Authors Christos Boutsidis, Malik Magdon-Ismail, Petros Drineas

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.21

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cited in

(11)

• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Column subset selection problem is UG-hard
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• Optimal column-based low-rank matrix reconstruction
• Column subset selection is NP-complete
• Frequent directions: simple and deterministic matrix sketching
• Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
• A note on sparse least-squares regression
• Literature survey on low rank approximation of matrices
• On the existence of a close to optimal cross approximation in the Frobenius norm
• Exponential inapproximability of selecting a maximum volume sub-matrix

This page was built for publication: Near Optimal Column-Based Matrix Reconstruction

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