Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
| Autor: | Ilse C. F. Ipsen, John T. Holodnak |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Rank (linear algebra) Dimension (graph theory) Machine Learning (stat.ML) Numerical Analysis (math.NA) Matrix multiplication Machine Learning (cs.LG) Combinatorics Computer Science - Learning Matrix (mathematics) Statistics - Machine Learning Product (mathematics) Singular value decomposition FOS: Mathematics Mathematics - Numerical Analysis Condition number Analysis Gramian matrix Mathematics |
| Zdroj: | SIAM Journal on Matrix Analysis and Applications. 36:110-137 |
| ISSN: | 1095-7162 0895-4798 |
| DOI: | 10.1137/130940116 |
| Popis: | Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-Carlo matrix multiplication algorithm by Drineas et al. that samples outer products, we present probabilistic bounds for the 2-norm relative error due to randomization. The bounds depend on the stable rank or the rank of A, but not on the matrix dimensions. Numerical experiments illustrate that the bounds are informative, even for stringent success probabilities and matrices of small dimension. We also derive bounds for the smallest singular value and the condition number of matrices obtained by sampling rows from orthonormal matrices. Update to title in third version. Major revisions in second version including new bounds and a more detailed experimental section. Submitted to SIMAX |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|