覆盖数和填充数

封面

很多统计学问题需要对一族随机变量进行考察，而往往该族变量数目并不是有限的。比如考察如何控制一个随机矩阵 的2范数（最大奇异值）:

其中 表示 维的单位球。处理这样的连续化问题无疑是十分麻烦的，因此如果能将该问题离散化，将减轻很多负担，这正是本文需要讨论的。

1 度量空间(Metric space)

首先定义度量空间 ,这里 是 的映射，并满足：

• 非负性: 对任意 成立，等号当且仅当 时成立.
• 对称性: 对任意 成立.
• 三角不等式： 对任意三元数组 成立 .

满足以上定义的测量空间是很常见的，比如 就是一个度量空间。

我们接下来将考量一个问题：多少个半径为 的“球”可以完全覆盖该空间？

2 覆盖数(Covering number)

定义1： 在度量空间 中，对一个固定的正数 ， 若集合 具有一种性质，即对 , 使得 . 则称 为 的 覆盖集。这样的 可以有很多个，最小的 的基数被称为 覆盖数，即 .

例2： 对区间 以及度量函数 , 定义向下取整函数 , 将该区间划分为 个子区间，且每个子区间的中心分别为 ,其中 每个子区间长度均为 。这些子区间的并包含区间 ，且对任意 ,总存在 ，使得 .因此

3 填充数(Packing number)

定义2： 在度量空间 中，对一个固定的正数 ，若集合 具有一种性质，即对 , 都有 . 则称 为 的 填充集。这样的 可以有很多个，记最大的 的基数被称为 填充数，即 .

覆盖数和填充数满足如下的不等式：

4 覆盖数和体积

首先引入Minkowski和: .

在入Minkowski和基础上，有如下定理：

定理1： 对于 上的两个范数 ,记 分别为相应的单位球(即 )。则 在范数 下的 覆盖数满足:

如果 , ,可以得到一个更简洁的不等式：

于是有

5 重返原问题

回到关于矩阵2范数的问题：

取 ,配备欧氏距离的 维单位球 可以被 集合 覆盖，且覆盖数 .

根据覆盖数的定义，对于任意 ,都存在 以及欧式范数小于 的 ,使得 .

由于 是由 确定的，我们将其分别暂记为 。这种标记实际上并不严谨，因为并不能保证只有唯一的 满足条件，但是方便起见，姑且如此表示。于是：

于是 。使用类似方法，可以得到

其中 .于是有：

其中 .

到此,我们成功将一个连续问题离散化了，这对使用集中不等式控制 的2范数有着很大的帮助（见Martin J Wainwright的HDS第10章第3节）。

参考文献

1. Wainwright, M. J. 2019. High-dimensional statistics: a non-asymptotic viewpoint. New York, NY: Cambridge University Press.
2. Vershynin, R. 2018.High-dimensional probability : an introduction with applications in data science. New York, NY: Cambridge University Press.