Relative errors for deterministic low-rank matrix approximations

DOI10.1137/1.9781611973402.53MaRDI QIDQ5384014zbMATH OpenOpenAlexFDO

Authors Mina Ghashami, Jeff M. Phillips

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

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

Abstract: We consider processing an n x d matrix A in a stream with row-wise updates according to a recent algorithm called Frequent Directions (Liberty, KDD 2013). This algorithm maintains an l x d matrix Q deterministically, processing each row in O(d l^2) time; the processing time can be decreased to O(d l) with a slight modification in the algorithm and a constant increase in space. We show that if one sets l = k+ k/eps and returns Q_k, a k x d matrix that is the best rank k approximation to Q, then we achieve the following properties: ||A - A_k||_F^2 <= ||A||_F^2 - ||Q_k||_F^2 <= (1+eps) ||A - A_k||_F^2 and where pi_{Q_k}(A) is the projection of A onto the rowspace of Q_k then ||A - pi_{Q_k}(A)||_F^2 <= (1+eps) ||A - A_k||_F^2. We also show that Frequent Directions cannot be adapted to a sparse version in an obvious way that retains the l original rows of the matrix, as opposed to a linear combination or sketch of the rows.

Recommendations

• Frequent directions: simple and deterministic matrix sketching
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• scientific article; zbMATH DE number 7049775
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• A fast and efficient algorithm for low-rank approximation of a matrix

Cited in

(13)

• Bounds for relative errors of complex matrix factorizations
• An improvement of the parameterized frequent directions algorithm
• On the accuracy of cross and column low-rank maxvol approximations in average
• Sampling-based dimension reduction for subspace approximation with outliers
• Frequent directions: simple and deterministic matrix sketching
• Robust frequent directions with application in online learning
• scientific article; zbMATH DE number 7049775 (Why is no real title available?)
• Communication-efficient distributed covariance sketch, with application to distributed PCA
• scientific article; zbMATH DE number 7404607 (Why is no real title available?)
• scientific article; zbMATH DE number 7164697 (Why is no real title available?)
• Eigenvalues of a matrix in the streaming model
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• Towards Optimal Moment Estimation in Streaming and Distributed Models

This page was built for publication: Relative errors for deterministic low-rank matrix approximations

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