论文标题
具有随机排名矢量的标准和跟踪估计
Norm and trace estimation with random rank-one vectors
论文作者
论文摘要
一些具有随机矢量的矩阵向量乘积通常足以获得一般基质规范的合理估计或对称阳性半明确矩阵的痕迹。已经提出了一些此类概率估计量，并分析了标准高斯和Rademacher随机载体。在这项工作中，我们考虑使用排名一的随机向量，即（较小）高斯或rademacher矢量的kronecker产品。采样此类向量不仅是便宜的，而且有时将矩阵与排名一号向量而不是通用向量相乘，因此有时也可以便宜得多。在这项工作中，理论和数值证据是，使用级别的一个而不是非结构化的随机向量仍会导致良好的估计。特别是，这表明我们的等级一估计量乘以适中的常数构成，概率很高，是利益量的上限。为下界提供了部分结果。说明了我们技术在矩阵函数的条件数估计中的应用。
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.
