A fast randomized algorithm for the approximation of matrices (Q952399): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Changed an Item
Property / describes a project that uses
 
Property / describes a project that uses: Algorithm 844 / rank
 
Normal rank

Revision as of 04:01, 29 February 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
    0 references
    0 references
    0 references
    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

    Identifiers