Note on sampling without replacing from a finite collection of matrices
David Gross and Vincent Nesme Institute for Theoretical Physics, Leibniz University Hannover, 30167 Hannover, Germany www.itp.uni-hannover.de/~davidg
Abstract
This technical note supplies an affirmative answer to a question raised in a recent pre-print in the context of a “matrix recovery” problem. Assume one samples $m$ Hermitian matrices $X_{1},\dots,X_{m}$ with replacement from a finite collection. The deviation of the sum $X_{1}+\dots+X_{m}$ from its expected value in terms of the operator norm can be estimated by an “operator Chernoff-bound” due to Ahlswede and Winter. The question arose whether the bounds obtained this way continue to hold if the matrices are sampled without replacement. We remark that a positive answer is implied by a classical argument by Hoeffding. Some consequences for the matrix recovery problem are sketched.
中文速览
矩阵复原（matrix recovery）问题要求从随机抽取的少量矩阵元素中重建一个低秩矩阵，而实际操作中样本应"不放回"地抽取，但已有分析为了技术便利都改用"有放回"抽样，由此带来额外误差和更弱的理论保证。本文指出，Hoeffding 1963年的一个经典凸性论证可以直接推广到矩阵值随机变量的情形，从而证明：对埃尔米特矩阵之和的算子范数做大偏差估计时，不放回抽样所对应的矩量母函数不超过有放回抽样的情形，即 Ahlswede–Winter 算子 Chernoff 界对不放回抽样同样成立。这一结论使矩阵复原分析中一个关键常数从 $O(\log n)$ 降至 $O(1)$，令所需观测数的上界提升约 4 倍，同时简化了若干已有证明，对后续量子态层析等噪声鲁棒性分析的改进效果更为显著。
原文 arXiv:1001.2738;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1001.2738v2