Practical sketching algorithms for low-rank matrix approximation
read the original abstract
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Sharp analysis of sketched least squares and randomized low-rank approximation
Random orthonormal matrices are minimax optimal for sketched least squares and rotation-invariant embeddings for randomized SVD, yielding the sharpest error bounds.
-
Scaling Federated Linear Contextual Bandits via Sketching
FSCLB scales federated linear contextual bandits with sketching to achieve over 90% lower computation and communication costs while preserving a near-optimal regret bound of O(sqrt(l d T)).
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.