Practical sketching algorithms for low-rank matrix approximation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Co-Occuring Directions Sketching for Approximate Matrix Multiply
We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occuring directions achieves a better error bound for AMM than other…
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independent subset of columns (a basis), regressi…
Open-Ended Question AnsweringregressionFew-Shot Data-Driven Algorithms for Low Rank Approximation
Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the …
Computational EfficiencyLearning the Positions in CountSketch
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g., low-rank approximation and regression. I…
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associa…