NORM AND TRACE ESTIMATION WITH RANDOM RANK-ONE VECTORS
NORM AND TRACE ESTIMATION WITH RANDOM RANK-ONE VECTORS
复制标题
DOI：
10.1137/20m1331718
复制
发表时间：
2021-01-01
影响因子：
1.5
通讯作者：
Kressner, Daniel
中科院分区：
文献类型：
--
作者：
Bujanovic, Zvonimir;Kressner, Daniel
对一般矩阵的范数或对称的正半定矩阵的迹，用一些随机向量的矩阵-向量乘法往往足以得到相当好的估计。对于标准高斯和Rademacher随机向量，已经提出并分析了几个这样的概率估计。在这项工作中，我们考虑使用排名第一的随机向量，即（较小的）高斯或Rademacher向量的Kronecker积。对这样的向量进行采样不仅更便宜，而且有时用秩一向量而不是一般向量乘以矩阵也更便宜。在这项工作中，理论和数值证据表明，使用秩1代替非结构化随机向量仍然可以得到很好的估计。特别地，证明了我们的秩一估计量与一个适度常数相乘，很可能构成感兴趣量的上界。给出了下界情况下的部分结果。说明了我们的技术在矩阵函数条件数估计中的应用。
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.