1 度量空间(Metric space)

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

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

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

2 覆盖数(Covering number)

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

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

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

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

首先引入Minkowski和: .

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

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

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

于是有

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

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

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

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

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

其中 .于是有：

其中 .

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

参考文献

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