A fast randomized algorithm for the approximation of matrices (Q952399): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.acha.2007.12.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4213311204 / rank | |||
Normal rank |
Revision as of 01:38, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A fast randomized algorithm for the approximation of matrices |
scientific article |
Statements
A fast randomized algorithm for the approximation of matrices (English)
0 references
12 November 2008
0 references
The authors propose a randomized procedure that, given an \(m \times n\) matrix \(A\) and a positive integer \(k\), approximates \(A\) with a matrix \(Z\) of rank \(k\). The algorithm relies on applying a structured \(l \times m\) random matrix \(R\) to each column of \(A\), where \(l\) is an integer near to, but greater than \(k\). The structure of \(R\) allows us to apply it to arbitrary \(m \times l\) vector at a cost proportional to \(m \log(l)\); the resulting procedure can construct a rank -\(k\) approximation \(Z\) from the entries of \(A\) at a cost proportional to \(mn \log(k)+l^2(m+n)\). The authors prove several bounds on the accuracy of the algorithm. The proposed algorithm operates reliably independently of the structure of the matrix \(A\), can access each column of \(A\) independently and at most twice, and parallelizes naturally. Numerical examples are also provided.
0 references
Lanczos method
0 references
singular value decomposition
0 references
QR factorization
0 references
random matrix
0 references
numerical examples
0 references