This article presents a randomized matrix-free method for approximating the trace of $f({\bf A})$, where ${\bf A}$ is a large symmetric matrix and $f$ is a function analytic in a closed interval containing the eigenvalues of ${\bf A}$. Our method uses a combination of stochastic trace estimation (i.e., Hutchinson's method), Chebyshev approximation, and multilevel Monte Carlo techniques. We establish general bounds on the approximation error of this method by extending an existing error bound for Hutchinson's method to multilevel trace estimators. Numerical experiments are conducted for common applications such as estimating the log-determinant, nuclear norm, and Estrada index, and triangle counting in graphs. We find that using multilevel techniques can substantially reduce the variance of existing single-level estimators.


翻译:本条提供了一种随机化的无基体方法,以接近 $f( {bf A}), 美元为大对称矩阵, 美元为在封闭间隔内的函数分析, 包含 $_bf A} 美元。 我们的方法使用一种混合的随机化跟踪估计( 即 Hutchinson 的方法)、 Chebyshev 近似和多级 Monte Carlo 技术。 我们通过将哈钦森 方法的现有误差扩展至多级跟踪测算器, 从而确定了这种方法近似误差的大致界限。 数字实验是针对对日志- 定义、 核规范 和 Extrada 指数 以及图形三角数等常见应用进行的。 我们发现, 使用多级技术可以大幅降低现有单级测算器的差异 。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
123+阅读 · 2020年11月20日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
145+阅读 · 2019年10月12日
“CVPR 2020 接受论文列表 1470篇论文都在这了
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
【泡泡一分钟】基于运动估计的激光雷达和相机标定方法
泡泡机器人SLAM
25+阅读 · 2019年1月17日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
VIP会员
相关资讯
“CVPR 2020 接受论文列表 1470篇论文都在这了
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
【泡泡一分钟】基于运动估计的激光雷达和相机标定方法
泡泡机器人SLAM
25+阅读 · 2019年1月17日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员