4.3 Article

NORM AND TRACE ESTIMATION WITH RANDOM RANK-ONE VECTORS

Journal

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Volume 42, Issue 1, Pages 202-223

Publisher

SIAM PUBLICATIONS
DOI: 10.1137/20M1331718

Keywords

norm of a matrix; trace of a matrix; stochastic estimator; rank-one vectors

Funding

  1. SNSF research project Low-rank updates of matrix functions and fast eigenvalue solvers
  2. Croatian Science Foundation [HRZZ-6268]
  3. COST grant Mathematical models for interacting dynamics on networks [CA18232]

Ask authors/readers for more resources

Utilizing rank-one random vectors for matrix-vector multiplication can lead to cost-effective and accurate estimations, serving as upper bounds for the quantity of interest with high probability.
A few matrix-vector multiplications with random vectors are often sufficient to obtain reasonably good estimates for the norm of a general matrix or the trace of a symmetric positive semi-definite matrix. Several such probabilistic estimators have been proposed and analyzed for standard Gaussian and Rademacher random vectors. In this work, we consider the use of rank-one random vectors, that is, Kronecker products of (smaller) Gaussian or Rademacher vectors. It is not only cheaper to sample such vectors but it can sometimes also be much cheaper to multiply a matrix with a rank-one vector instead of a general vector. In this work, theoretical and numerical evidence is given that the use of rank-one instead of unstructured random vectors still leads to good estimates. In particular, it is shown that our rank-one estimators multiplied with a modest constant constitute, with high probability, upper bounds of the quantity of interest. Partial results are provided for the case of lower bounds. The application of our techniques to condition number estimation for matrix functions is illustrated.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.3
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available