Error Estimation for Sketched SVD
In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching an SVD is that the user does not know how far the sketched singular vectors/values are from the exact ones. Indeed, the user may be forced to rely on analytical worst-case error bounds, which do not account for the unique structure of a given problem. As a result, the lack of tools for error estimation often leads to much more computation than is really necessary. To overcome these challenges, this paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. In particular, this approach allows the user to inspect the quality of a rough initial SVD, and then adaptively predict how much extra work is needed to reach a given error tolerance. Meanwhile, from a computational standpoint, the proposed method incurs only minor cost, because it operates on the (small) output of a sketching algorithm, and it requires no passes over the (large) matrix being factored. Lastly, the proposed method is supported by theoretical guarantees and a very encouraging set of experimental results.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Error Estimation for Sketched SVD via the Bootstrap
In order to compute fast approximations to the singular value decompositions (SVD) of very large matrices, randomized sketching algorithms have become a leading approach. However, a key practical difficulty of sketching …
Least Squares Estimation Using Sketched Data with Heteroskedastic Errors
Researchers may perform regressions using a sketch of data of size $m$ instead of the full sample of size $n$ for a variety of reasons. This paper considers the case when the regression errors do not have constant varian…
regressionSketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees
Randomized algorithms are important for solving large-scale optimization problems. In this paper, we propose a fast sketching algorithm for least square problems regularized by convex or nonconvex regularization function…
Sparse LearningCommunication-Efficient Federated Learning with Sketching
Existing approaches to federated learning suffer from a communication bottleneck as well as convergence issues due to sparse client participation. In this paper we introduce a novel algorithm, called FedSketchedSGD, to o…
Federated LearningWhat is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
Randomized sketching accelerates large-scale numerical linear algebra by reducing computational complexity. While the traditional sketch-and-solve approach reduces the problem size directly through sketching, the sketch-…