机器学习与数据科学博士生系列论坛（第五十三期）—— Approximate Matrix Functions via Sketching and Variance Reduction

摘要：
Several unbiased estimators are designed to estimate matrix functions, such as the trace, matrix diagonal, norm, matrix multiplication, etc. These estimators are often closely related to the JL-transform, and the variance can be expressed as a norm of the matrix. In the framework of matrix-vector multiplication, Meyer et al. [2022] propose an algorithm based on variance reduction, which reduces the complexity of the trace estimation algorithm, and they also provide the exact lower bound of complexity. The same method, which is abstracted into a framework, has also been applied to other linear algebra problems such as diagonal estimation and norm estimation, and similar acceleration has been achieved.

In this talk, we will briefly introduce the approach of trace estimation [Meyer et al. 2022] and the results of similar problems. The techniques can also be easily extended to other problems, such as approximation matrix multiplication and norm estimation. We will also briefly discuss its connection with regression-adjusted control variates.

论坛简介：该线上论坛是由张志华教授机器学习实验室组织，每两周主办一次（除了公共假期）。论坛每次邀请一位博士生就某个前沿课题做较为系统深入的介绍，主题包括但不限于机器学习、高维统计学、运筹优化和理论计算机科学。