L

Liushixiang

V1

2022/10/23阅读:25主题:默认主题

覆盖数和填充数

封面

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

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

1 度量空间(Metric space)

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

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

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

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

2 覆盖数(Covering number)

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

例1:五边型区域$ \mathbb{T} N(\epsilon ; \mathbb{T}, || \cdot ||_2) \le 7.$
例1:五边型区域 被7个二维“球”覆盖,这说明

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

3 填充数(Packing number)

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

例3:五边型区域$ \mathbb{T} $被10个二维“球”填充,任两个球(圆)心距离大于,这说明
例3:五边型区域 被10个二维“球”填充,任两个球(圆)心距离大于 ,这说明

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

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.

分类:

数学

标签:

高等数学

作者介绍

L
Liushixiang
V1