Liushixiang
2022/10/23阅读:54主题:默认主题
覆盖数和填充数
封面
很多统计学问题需要对一族随机变量进行考察,而往往该族变量数目并不是有限的。比如考察如何控制一个随机矩阵 的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节)。
参考文献
-
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.
作者介绍