欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

UA MATH567 高维统计III 随机矩阵6 亚高斯矩阵的范数

发布时间：2025/4/14 编程问答 40 豆豆
生活随笔 收集整理的这篇文章主要介绍了 UA MATH567 高维统计III 随机矩阵6 亚高斯矩阵的范数 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

UA MATH567 高维统计III 随机矩阵6 亚高斯矩阵的范数

在前五讲的理论基础上，我们现在开始正式讨论随机矩阵。假设AAA是一个m×nm \times nm×n的随机矩阵，它的元素AijA_{ij}Aij​是互相独立的零均值的亚高斯随机变量，关于它的范数有下面的结论

随机矩阵的范数 K=max⁡i,j∥Aij∥ψ2K=\max_{i,j}\left\| A_{ij} \right\|_{\psi_2}K=maxi,j​∥Aij​∥ψ2​​, ∀t>0\forall t>0∀t>0
P(∥A∥≲K(m+n+t))≥1−2e−t2P(\left\| A\right\| \lesssim K(\sqrt{m}+\sqrt{n}+t)) \ge 1-2e^{-t^2}P(∥A∥≲K(m​+n​+t))≥1−2e−t2

这个结果说明矩阵AAA的范数的尾部概率也具有亚高斯性。如果AAA是n×nn \times nn×n的对称阵，则
P(∥A∥≲K(n+t))≥1−4e−t2P(\left\| A\right\| \lesssim K(\sqrt{n}+t)) \ge 1-4e^{-t^2}P(∥A∥≲K(n​+t))≥1−4e−t2

证明

第一步，我们先考虑一下算子范数，
∥A∥=max⁡x∈Sn−1y∈Sm−1⟨Ax,y⟩\left\| A \right\| = \max_{x \in S^{n-1} \\ y \in S^{m-1}}\langle Ax,y\rangle∥A∥=x∈Sn−1y∈Sm−1max​⟨Ax,y⟩

存在x∈Sn−1,y∈Sm−1x \in S^{n-1},y \in S^{m-1}x∈Sn−1,y∈Sm−1使得∥A∥=⟨Ax,y⟩\left\| A \right\|=\langle Ax,y\rangle∥A∥=⟨Ax,y⟩，假设N\mathcal{N}N是Sn−1S^{n-1}Sn−1的一个ϵ\epsilonϵ-net（根据第四讲的讨论，我们总是可以用一个球框住这样的集网，因此不失一般性，我们可以构造cardinality满足∣N∣<9n,∣M∣<9m|\mathcal{N}|<9^n,|\mathcal{M}|<9^m∣N∣<9n,∣M∣<9m的集网），M\mathcal{M}M是Sm−1S^{m-1}Sm−1的一个ϵ\epsilonϵ-net，则根据定义∃x0∈N,∃y0∈M\exists x_0 \in \mathcal{N},\exists y_0 \in \mathcal{M}∃x0​∈N,∃y0​∈M，∥x−x0∥2≤ϵ,∥y−y0∥2≤ϵ\left\| x-x_0\right\|_2 \le \epsilon,\left\| y-y_0\right\|_2 \le \epsilon∥x−x0​∥2​≤ϵ,∥y−y0​∥2​≤ϵ，计算
⟨Ax0,y0⟩=⟨Ax,y⟩+⟨A(x−x0),y⟩+⟨Ax0,y0−y⟩\langle Ax_0,y_0\rangle=\langle Ax,y\rangle+\langle A(x-x_0),y\rangle+\langle Ax_0,y_0-y\rangle⟨Ax0​,y0​⟩=⟨Ax,y⟩+⟨A(x−x0​),y⟩+⟨Ax0​,y0​−y⟩

其中第二项满足
⟨A(x−x0),y⟩≥−∥A(x−x0)∥2∥y∥2=−∥A(x−x0)∥2≥−ϵ∥A∥\langle A(x-x_0),y\rangle\ge -\left\| A(x-x_0)\right\|_2\left\| y\right\|_2 \\ =-\left\| A(x-x_0)\right\|_2 \ge -\epsilon \left\| A \right\| ⟨A(x−x0​),y⟩≥−∥A(x−x0​)∥2​∥y∥2​=−∥A(x−x0​)∥2​≥−ϵ∥A∥

类似地，第三项满足
⟨Ax0,y0−y⟩≥−ϵ∥A∥\langle Ax_0,y_0-y\rangle \ge -\epsilon \left\| A \right\|⟨Ax0​,y0​−y⟩≥−ϵ∥A∥

因此
∥A∥≤11−2ϵ⟨Ax0,y0⟩≤11−2ϵmax⁡x∈Ny∈M⟨Ax,y⟩\left\| A \right\| \le \frac{1}{1-2\epsilon}\langle Ax_0,y_0\rangle \le \frac{1}{1-2\epsilon}\max_{x \in \mathcal{N} \\ y \in \mathcal{M}}\langle Ax,y\rangle∥A∥≤1−2ϵ1​⟨Ax0​,y0​⟩≤1−2ϵ1​x∈Ny∈Mmax​⟨Ax,y⟩

第二步，我们讨论随机矩阵的二次型，∀x∈N,y∈M\forall x \in \mathcal{N}, y \in \mathcal{M}∀x∈N,y∈M，
⟨Ax,y⟩=∑i=1n∑j=1mAijxixj\langle Ax,y\rangle=\sum_{i=1}^n \sum_{j=1}^m A_{ij}x_ix_j⟨Ax,y⟩=i=1∑n​j=1∑m​Aij​xi​xj​

于是根据推广Hoeffding不等式的第一个结论，∃C>0\exists C>0∃C>0，
∥⟨Ax,y⟩∥ψ2≤C∑i=1n∑j=1m∥Aijxixj∥ψ2=C∑i=1n∑j=1mxi2yj2∥Aij∥ψ2≤C∑i=1n∑j=1mxi2yj2K2=CK2\left\| \langle Ax,y\rangle\right\|_{\psi_2} \le C \sum_{i=1}^n \sum_{j=1}^m \left\| A_{ij}x_ix_j\right\|_{\psi_2} \\ = C \sum_{i=1}^n \sum_{j=1}^mx_i^2y_j^2 \left\| A_{ij}\right\|_{\psi_2} \le C \sum_{i=1}^n \sum_{j=1}^mx_i^2y_j^2 K^2 = CK^2∥⟨Ax,y⟩∥ψ2​​≤Ci=1∑n​j=1∑m​∥Aij​xi​xj​∥ψ2​​=Ci=1∑n​j=1∑m​xi2​yj2​∥Aij​∥ψ2​​≤Ci=1∑n​j=1∑m​xi2​yj2​K2=CK2

这说明⟨Ax,y⟩\langle Ax,y\rangle⟨Ax,y⟩是亚高斯的。

第三步，使用亚高斯性，
P(⟨Ax,y⟩≥u)≤2e−cu2/K2,∃c>0P(\langle Ax,y\rangle \ge u) \le 2 e^{-cu^2/K^2},\exists c>0P(⟨Ax,y⟩≥u)≤2e−cu2/K2,∃c>0

于是
P(max⁡x∈Ny∈M⟨Ax,y⟩≥u)≤∑x∈Ny∈MP(⟨Ax,y⟩≥u)≤9m+n2e−cu2/K2=2e(m+n)log⁡9−cu2/K2P(\max_{x \in \mathcal{N} \\ y \in \mathcal{M}}\langle Ax,y\rangle \ge u) \le \sum_{x \in \mathcal{N} \\ y \in \mathcal{M}} P(\langle Ax,y\rangle \ge u) \\ \le 9^{m+n}2 e^{-cu^2/K^2}=2e^{(m+n)\log 9-cu^2/K^2}P(x∈Ny∈Mmax​⟨Ax,y⟩≥u)≤x∈Ny∈M∑​P(⟨Ax,y⟩≥u)≤9m+n2e−cu2/K2=2e(m+n)log9−cu2/K2

因为uuu可以任意选取，为了使这个尾部概率尽可能小，我们希望通过选取uuu使得这个概率的上界在m,nm,nm,n趋于无穷时收敛到0，一种可行的选取是
u=C′K(m+n+t)u2≥C′2K2(m+n+t)u = C'K(\sqrt{m}+\sqrt{n}+t) \\ u^2 \ge C'^2K^2(m+n+t)u=C′K(m​+n​+t)u2≥C′2K2(m+n+t)

其中C′>0C'>0C′>0是个常数，于是
2e(m+n)log⁡9−cu2/K2≥2e(m+n)log⁡9−cC′2(m+n)−cC′2t2e^{(m+n)\log 9-cu^2/K^2} \ge 2e^{(m+n)\log 9-cC'^2(m+n)-cC'^2t}2e(m+n)log9−cu2/K2≥2e(m+n)log9−cC′2(m+n)−cC′2t

选取C′C'C′使得
(m+n)log⁡9−cC′2(m+n)<0,cC′2≥1(m+n)\log 9-cC'^2(m+n)<0,cC'^2 \ge 1(m+n)log9−cC′2(m+n)<0,cC′2≥1

则
2e(m+n)log⁡9−cC′2(m+n)−cC′2t≥2e−2t22e^{(m+n)\log 9-cC'^2(m+n)-cC'^2t} \ge 2e^{-2t^2}2e(m+n)log9−cC′2(m+n)−cC′2t≥2e−2t2

这样我们就说明了∃C>0\exists C>0∃C>0
P(∥A∥≤CK(m+n+t))≥1−2e−t2P(\left\| A\right\| \le C K(\sqrt{m}+\sqrt{n}+t)) \ge 1-2e^{-t^2}P(∥A∥≤CK(m​+n​+t))≥1−2e−t2

第四步，说明对称的情况，如果AT=AA^T=AAT=A，我们是不能直接用第三步的结果的，因为前三步得到的结论要求AAA的所有分量都是独立的，而对称的矩阵自带约束Aij=AjiA_{ij}=A_{ji}Aij​=Aji​，因此关于主对角线对称的两个元素必定不独立。一种拆分方法是我们把对称矩阵沿主对角线拆开：
A=A++A−A=A^+ + A^-A=A++A−

其中A+A^+A+表示下三角部分(包含主对角线，上三角部分为0)，A−A^-A−表示上三角部分（不包含主对角线，主对角线及下三角部分为0），于是
∥A∥=∥A+∥+∥A−∥\left\| A\right\| =\left\| A^+\right\|+\left\| A^-\right\| ∥A∥=∥∥​A+∥∥​+∥∥​A−∥∥​

分别对∥A+∥\left\| A^+\right\|∥A+∥与∥A−∥\left\| A^-\right\|∥A−∥使用前三步的结论即可。

总结

以上是生活随笔为你收集整理的UA MATH567 高维统计III 随机矩阵6 亚高斯矩阵的范数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。