Relative Errors for Deterministic Low-Rank Matrix Approximations

DOI10.1137/1.9781611973402.53zbMath1421.68222arXiv1307.7454OpenAlexW1661223625MaRDI QIDQ5384014

Jeff M. Phillips, Mina Ghashami

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.7454

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Unnamed Item ⋮ Optimal CUR Matrix Decompositions ⋮ Sampling-based dimension reduction for subspace approximation with outliers ⋮ An improvement of the parameterized frequent directions algorithm ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Unnamed Item