Random orthonormal matrices are minimax optimal for sketched least squares and rotation-invariant embeddings for randomized SVD, yielding the sharpest error bounds.
Tropp, Alp Yurtsever, Madeleine Udell, and V olkan Cevher
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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.
years
2026 2verdicts
UNVERDICTED 2representative citing papers
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)).
citing papers explorer
-
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)).