跳转至

A large deviation inequality for the rank of a random matrix

作者: Mark Rudelson
来源: Annals of Probability
主题: 高维统计 / 随机矩阵
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

随机矩阵的奇异性（singularity）与秩亏损（rank deficiency）问题：对 \(n \times n\) 随机矩阵 \(A\)，刻画 \(\text{rank}(A) < n\)（即奇异）或 \(\text{rank}(A) \le n-k\)（秩亏损 \(k\)）的概率。这类概率界是非渐近随机矩阵理论的核心支柱——它们直接控制最小奇异值的尾部行为，是高维统计中估计量可逆性、谱聚类稳定性、压缩感知恢复条件的概率基础。该方向已高度成熟：奇异性概率的指数界已由 Tikhomirov (2018) 推到常数底数 \((1/2+o(1))^n\)（对 Bernoulli 情形接近最优）；小奇异值分布已有相容的概率界（如 Rudelson & Vershynin 2007 给出阶为 \(n^{-1/2}\) 的最小奇异值下界）。但秩亏损的大偏差——即概率随 \(k n\) 指数衰减而非仅仅随 \(n\) 指数衰减——此前无系统性结果，这正是本文填补的空白。

发展脉络（history）

奠基阶段：Littlewood-Offord 问题与奇异性概率的早期界
Kahn, Komlós, Szemerédi (1995) 首次证明 Bernoulli 随机矩阵奇异概率 \( \le 2^{-cn}\)。Rudelson & Vershynin (2007) [2] 将 Littlewood-Offord 技巧与现代几何方法结合，得到更一般的界：“the smallest singular value is of order \(n^{-1/2}\)，which is optimal for Gaussian matrices”，并给出最优的尾部估计。该文奠定了“几何方法”（覆盖 + 不可压缩分解）成为后续所有非渐近可逆性证明的范式。

主要进展：对称矩阵、稀疏矩阵与最优指数
- Vershynin (2011) [3] 证明对称随机矩阵奇异性概率 \(\le \exp(-n^c)\)，且谱在最优尺度上局域化。
- Tikhomirov (2018) [8] 对 Bernoulli 情形得到 ** \((1/2+o(1))^n\) ，逼近下界，[作者引用句：“The asymptotically optimal exponent has been recently obtained by Tikhomirov”]。
- Jain, Sah, Sawhney (2020) [5] 将指数界推广到任意有限支撑分布，[引用句：“then with probability \(1-4^{-kn}\)，the kernel ... either consists of vectors close to sparse，or does not contain any vector with a problematic arithmetic structure”]——注意该文已经得到 \(4^{-kn}\) 型的概率界，但其依赖于离散分布且仅对 \(k = O(\sqrt{n})\)** 有效，且证明框架（压缩/不可压缩分解）与本文紧密相关。

当前 frontier：非 subgaussian / 非 i.i.d. 情形 & 秩亏损的大偏差
- Livshyts (2018) [9] 引入随机舍入（random rounding）技巧，对重尾 entries 给出最小奇异值的小球概率界。
- Livshyts, Tikhomirov, Vershynin (2019) [14] 移除 i.i.d. 行假设，得到非齐次矩阵的最优界，其核心是介绍 随机最小公分母 (RLCD)。
- 在奇异性概率方面，上界均为 \( \exp(-cn) \) 量级，不依赖于 \(k\)。本文 则给出 \(1 - \exp(-c' k n)\) 的秩亏损概率下界（上界？实际上是下界——rank ≥ n-k 的概率下界），首次将指数从 \(n\) 提高到 \(kn\)（对 \(k \le c\sqrt{n}\)）。这是方向上的一次量级提升。

本文的位置：紧跟在 Jain et al. (2020) 的 \(4^{-kn}\) 型界之后，但覆盖分布更广（subgaussian）且证明更简洁；同时是目前已知对一般 subgaussian 矩阵秩亏损大偏差的唯一结果。

子线索聚类

  1. 几何方法（压缩/不可压缩分解 + 覆盖）：Rudelson & Vershynin (2007)、Vershynin (2011)、Rudelson (2005) [7] 构成主线。本文采用同一条路线。
  2. 随机舍入与 LCD 技巧：Livshyts (2018) [9]、Livshyts et al. (2019) [14] 用于处理重尾或非 i.i.d. entries。本文未使用，但提及可与 Nguyen (2017) [10] 结合获得带 \(\exp(c k n)\) 误差项的奇异值下界。
  3. 离散 / 有限支撑 entries 的优化指数：Tikhomirov (2018) [8]、Jain et al. (2020) [5]。这些结果有更优的底数，但局限于离散分布。本文结果对 subgaussian 连续分布（如高斯）也成立。
  4. 对称 / Wigner 矩阵的奇异性：Campos et al. (2022) [16] 得到对称情况的最优界。本文仅处理非对称情形。

这个方向在追问的核心问题（2-4 个）

  • 问题 1：秩亏损概率能否达到 \( \exp(-c k n)\) （即指数依赖乘积 \(kn\)）？若可，\(k\) 的最大允许范围是多少（\(c\sqrt{n}\)？还是整个 \([n]\)）？
  • 问题 2：底数 \(c'\) 的依赖物是什么（subgaussian 范数、方差）？能否对具体分布（如 Bernoulli）逼近精确常数？
  • 问题 3：\(k\) 与 \(n\) 的比例限制（\(k \le c\sqrt{n}\)）是否是本质的？能否通过更强的 anti-concentration 假设突破到 \(k = o(n)\)？
  • 问题 4：对称矩阵、稀疏矩阵、相关 entries 情形下的对应界是否存在？

当前主流方法：几何覆盖 + 压缩/不可压缩分解（用于小奇异值）；Littlewood-Offord 型 anti-concentration（用于控制算术结构）。瓶颈在于：LCD 技巧和覆盖的构造在 \(k\) 较大时，每个被覆盖向量的长度控制与覆盖数产生 \(kn\) 乘积项——这正是本文突破的关键。

⚠️ 作者的 framing（必须明确标注成“这是作者的说法”）

作者在引言中说：“the probability that a random matrix is singular decays at least exponentially in \(n\)，but ... nothing is known about the rank deficiency probability when \(k\) grows with \(n\)”。他把缺口 frame 成：所有已有工作只关心奇异性（\(k=0\)），没有人在一般 subgaussian 情形下研究过秩亏损的大偏差。因此本文成为“显然的下一步”。
淡化/回避：① Jain et al. (2020) 实际上对离散分布给出了 \(4^{-kn}\) 的界，但作者只说“an exponential bound ... in a more general context”（指 Tikhomirov），回避了 Jain et al. 的 \(kn\) 型界与本文结果在形式上的一致——文中引用了 [5] 作为框架的一部分，但未明确对比指数幂的大小。② 未讨论对称矩阵或稀疏矩阵的秩亏损，尽管 Campos et al. (2022) 已给出对称矩阵最小奇异值的最佳常数界，但未涉及秩亏损概率。
明显该被引 / 该存在、却没出现在 intro 里的：Kahn, Komlós, Szemerédi (1995) 最早的指数界未被引用；Tao & Vu (2006) 关于“Uniform almost-orthogonality”的结果也未引用。这可能是作者有意省略奠基性文献，但仍值得研究者去查证这些早期工作是否隐含了秩亏损的概率测度。

张力

未见明显对立引用。各被引工作互相补充：几何方法派（Rudelson, Vershynin）与离散优化派（Tikhomirov, Jain-Sah-Sawhney）的证明风格虽有差异，但结论方向一致——指数衰减。本文属于几何方法派的一个推广。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • \(A_n = (a_{ij})_{i,j=1}^n\)：\(n \times n\) 随机矩阵。
  • 条目 \(\{a_{ij}\}_{i,j}\) 是 i.i.d. 实值随机变量。
  • 分布假设：\(a_{ij}\) 非常数，均值为零（可中心化），且subgaussian：存在常数 \(\sigma > 0\) 使得对一切 \(t>0\) 有 \(\mathbb{P}(|a_{ij}| \ge t) \le 2 \exp(-t^2/(2\sigma^2))\)。记 subgaussian 范数 \(\|a_{ij}\|_{\psi_2} = \inf\{t>0: \mathbb{E}\exp(a_{ij}^2/t^2) \le 2\} = \sigma_0\)。
  • 秩 (rank)：矩阵 \(A_n\) 的列空间维数。事件 \(\text{rank}(A_n) \ge n-k\) 指矩阵至少缺 \(k\) 秩（即列空间维数 \(\ge n-k\)），等价于存在至少 \(k\) 个线性无关的零向量（即核维数 \(\le k\)）。
  • 可观测数据：只有一个 \(n \times n\) 随机矩阵 \(A_n\) 的样本（独立同分布条目）。我们只观测到矩阵本身，不观测其奇异值分解或特征向量。
  • 目标量（estimand）：概率 \(\mathbb{P}(\text{rank}(A_n) \ge n-k)\) 的下界，作为 \(n\) 和 \(k\) 的函数。
  • 参数：\(n\) 是维数（矩阵大小），\(k\) 是秩亏损的容忍度（允许丢失的秩数），满足 \(k \le c\sqrt{n}\)（\(c\) 为与分布有关的绝对常数）。
  • 关键记号：
  • 记 \(\kappa = \mathbb{E} a_{ij}^2 / \|a_{ij}\|_{\psi_2}^2\)（归一化的二阶矩），论文中用 \(c_0, c_1, c_2, c'\) 等表示依赖于 \(\kappa\) 和各阶矩的通用常数。
  • 单位球面 \(S^{n-1} = \{x \in \mathbb{R}^n: \|x\|_2 = 1\}\)。
  • 对向量 \(x \in S^{n-1}\)，\(\|Ax\|_2\) 是矩阵-向量乘积的 Euclidean 范数。若 \(x\) 属于核空间，则 \(\|Ax\|_2 = 0\)。
  • \(\text{span}\) 指线性张成。

第二步：讲最小内核

最简特例：\(A_n\) 的条目为 i.i.d. 标准正态分布 \(N(0,1)\)；\(n\) 较大，\(k = \lfloor \sqrt{n} \rfloor\)。我们要证明：

\[\mathbb{P}(\text{rank}(A_n) \ge n - \sqrt{n}) \ge 1 - \exp(-c' \cdot \sqrt{n} \cdot n) = 1 - \exp(-c' n^{3/2}).\]

这比奇异性概率（对应 \(k=0\)）的指数界 \(\exp(-cn)\) 强得多。

证明核心思路（用最小特例解释）：
秩亏损意味着存在一个单位向量 \(x \in S^{n-1}\) 使得 \(\|Ax\|_2\) 很小（甚至是零）。更精确地，若 \(\text{rank}(A) \le n-k\)，则核维数至少 \(k\)，因此存在一个 \(k\) 维子空间 \(\mathbb{R}^n\)，其上每个向量的 \(A\)-范数都为零。反过来，为了证明秩亏损概率很小，我们证明：对任意 \(k\) 维子空间 \(L\)（即 span 给定），\(\|Ax\|_2\) 对多数 \(x \in L \cap S^{n-1}\) 都“不小”。但直接对子空间整体处理很困难。

关键技巧：构造 \(k\) 个正交向量 \(v_1,\dots,v_k\)，然后分两步论证：
1. 对每个单独的方向 \(v_i\)，利用 subgaussian 的 tail bound 得到 \(\|A v_i\|_2^2 \ge n \sigma^2 / 2\) 以高概率（需要一点 anti-concentration，但高斯情形直接就是 \(\chi^2_n\)）。
2. 但这些方向本身是随机的（因为 \(v_i\) 的选取依赖于 \(A\)？不，我们必须对所有可能的子空间进行覆盖）。解决方法是：覆盖全体 \(k\)-维子空间的微商空间（Grassmannian）的 \(\epsilon\)-net，然后对每个网中的子空间应用 bound。覆盖数 \(\lesssim (C n)^k\)（Grassmannian 的度量熵）。取并，用 union bound：

\[\mathbb{P}(\exists \text{子空间 } L \text{ s.t. 核维数 } \ge k) \le (\text{网大小}) \cdot \exp(-cn) \approx \exp(k \log n - cn).\]

当 \(k \ll n/\log n\) 时，这是 \(\exp(-c n)\)。但这只得到 \(n\) 指数，不是 \(kn\)。

如何得到 \(kn\) 指数？ 上面丢失了因子 \(k\)。本文的核心进步在于：不覆盖整个 Grassmannian，而是直接构造一个随机化的 \(k\)-维子空间，然后对该子空间的“坏事件”进行控制。更具体地，作者考虑 \(A\) 的前 \(n-k\) 行组成的 \((n-k)\times n\) 的子矩阵 \(B\)，并证明：除非 \(A\) 的前 \(n-k\) 行有非常特殊的算术结构（由离散性造成），否则 \(B\) 的核最多包含“稀疏”向量，而这些向量可以用 \(\epsilon\)-net 覆盖（覆盖数约 \(\exp(O(k \log(n/k)))\)）。然后对每个稀疏向量 \(x\)，用次指数型的 \(\|B x\|_2\) 小偏差概率（基于 Hanson-Wright 不等式）控制其贡献，最后得到总概率 \(\le \exp(-c k n)\)。

最小例子下的简化（选择高斯分布）：
- 令 \(B\) 为 \(A\) 的前 \(m = n-k\) 行（\(m = n - \sqrt{n}\)）。
- 若 \(\text{rank}(A) \le n-k\)，则存在非零 \(x \in \mathbb{R}^n\) 使得 \(B x = 0\)（因为 \(B\) 的行数小于列数，核非平凡）。
- 正则化 \(x\) 使其 \(\|x\|_2 = 1\)。
- 关键引理（压缩性引理，Rudelson 2007）：对任何单位向量 \(x\)，要么 \(x\) 是“稀疏”的（即除少数坐标外都接近于零——可压缩），要么 \(\|B x\|_2\) 不太小（以高概率）。
- 对稀疏情形：覆盖所有可能稀疏支撑集（约 \(\binom{n}{k}\) 个）和支撑内的方向（约 \(\exp(O(k \log(n/k)))\)），总覆盖数 \(\approx \exp\left(O\left(k \log \frac{en}{k}\right)\right)\)。
- 对每个被抓到的 \(x\)，由于 \(B\) 的行数 \(m = n-k\)，\(\|B x\|_2^2 \approx (n-k) \sigma^2\) 以极大概率（Hanson-Wright）。
- 唯有当 \(x\) 精确位于核中时，\(\|B x\|_2 = 0\) 才发生，其概率由 \(\|B x\|_2\) 的 tail bound 控制，对固定 \(x\) 可得 \(\le \exp(-c (n-k))\)（因为 \(\|B x\|_2^2\) 是 \(n-k\) 个独立 chi-squared 和一个积，球壳测度）。
- Union bound：总概率 \(\lesssim \exp\left(O\left(k \log \frac{en}{k}\right) - c (n-k)\right)\)。当 \(k \le c\sqrt{n}\) 时，\(k \log(n/k) \le c' n\) 且 \(k \ll n\)，所以指数为 \(c' n - c n = -c^* n\)，仍只得到 \(n\) 指数。要得到 \(kn\)，需要将 \(n\) 换成 \(k n\) 的乘积——这来自更精细的 anti-concentration：对固定 \(x\)，\(\|B x\|_2\) 的分布依赖于 \(B x\) 的方差 \(= \|x\|_2^2\)，但核中向量 \(x\) 可能由其坐标的不同尺度支配；通过将 \(x\) 的支撑大小限制在更小范围（如 \(\Theta(k)\)），可使每个坐标上的方差贡献为 \(O(1/k)\)，从而得到 \(k\) 倍增益。这正是论文技术部分的核心——通过压缩性分类和 LCD 控制，使得 \(\|B x\|_2\) 小偏差概率提升到 \(\exp(-c k m)\)，最终得到 \(\exp(-c' k n)\)。

（对于 \(N(0,1)\) 特例，在 \(k = \sqrt{n}\) 时，清洁参数下可推导出 \(\exp(-c n^{3/2})\)，但需用到 \(\|B x\|_2\) 的更高阶矩和尾概率以匹配覆盖数。实际上论文的证明适用于一般 subgaussian，高斯情形只是其中一个特例。）

一句话总结最小内核：核心困难是从 \(\exp(-c n)\) 提升到 \(\exp(-c k n)\)，本质因为覆盖数（约 \(\exp(O(k \log n))\)）与每个被覆盖向量的反概率（原先 \(\exp(-c n)\)）的乘积无法产生 \(k n\)；通过空间分解成“不可压缩”部分并用 随机 LCMD (Least Common Multiple Degree) 或更精细的网构造，使得反概率提高到 \(\exp(-c k \cdot (\text{行数}))\)，从而与覆盖数的 \(k\) 阶多项式因子匹配后得到 \(\exp(-c k n)\)。

三、这篇论文做了什么

三句话

① 研究了subgaussian i.i.d. 随机矩阵秩亏损的大偏差：对任意 \(k \le c\sqrt{n}\)，证明排名至少 \(n-k\) 的概率不低于 \(1-\exp(-c' k n)\)。② 核心工具是几何方法（压缩/不可压缩分解）与Hanson-Wright 型次指数 tail bound 的组合，并引入一个基于“行数-坐标”双参数的网格构造策略。③ 主要结论是第一个对一般 subgaussian 分布成立的 \(k n\) 指数秩亏损概率下界，改进了之前奇异性概率的 \(\exp(-c n)\) 上界（当 \(k\) 增长时指数显著放大）。

关键设定与假设

  • 设定：\(A = (a_{ij})\)，\(n \times n\)，i.i.d. 条目，common distribution \(\xi\)，满足 \(\mathbb{E}\xi = 0\)，\(\mathbb{E}\xi^2 = \sigma^2 > 0\)，且 \(\|\xi\|_{\psi_2} < \infty\)（subgaussian）。
  • 假设：非常数（否则退化）。不假设对称性、稀疏性、独立性之外的任何结构。
  • 与已有文献对比：相比 Rudelson (2005) 和 Rudelson-Vershynin (2007) 对最小奇异值的界（也是 subgaussian），本文延伸到了秩亏损概率；相比 Tikhomirov (2018) 的离散界，本文不要求有限支撑；相比 Jain et al. (2020) 的 \(4^{-kn}\) 界，本文推广到了 subgaussian 且证明更本质（后者依赖离散性）。
  • 假设放宽之处：未要求分布对称或行独立；未要求分布有密度或连续。唯一要求是 subgaussian。
  • 假设强化之处：未处理重尾（如仅有二阶矩）的情形——那需要 Livshyts (2018) 的随机舍入技巧，作者在文末提及可作为未来工作。

主要结果

Theorem 1.1（核心定理）：存在绝对常数 \(c, c' > 0\)，使得对任意 subgaussian 非退化分布，对一切 \(k \le c\sqrt{n}\) 有

\[\mathbb{P}(\text{rank}(A) \ge n-k) \ge 1 - \exp(-c' k n).\]

等价地，奇异性概率 \( \le \exp(-c' n)\) 被推广为“至少缺 \(k\) 秩”的概率 \( \le \exp(-c' k n)\)。

  • 直觉：当 \(k\) 增大时，秩亏损越来越不可能——概率以 \(k n\) 的指数衰减，比 \(k\) 固定时的 \(\exp(-c n)\) 快得多。
  • 必要条件：\(k \le c\sqrt{n}\)。这个条件意味着 \(k\) 不能超过 \(n\) 的平方根量级。作者指出：“the bound... holds for any \(k \le c_0 \sqrt{n}\)，where \(c_0\) depends on the subgaussian norm”。若 \(k > \sqrt{n}\)，该证明将失效（覆盖数超过指数收益）。
  • 解决的技术难点：之前的奇异性证明中，覆盖的 \(\epsilon\)-net 大小约 \(\exp(n)\)，导致乘积概率中只能提取出 \(n\) 指数。本文通过对核中向量的压缩性分解，将高维向量的支撑集大小限制在 \(O(k)\)，从而覆盖数降为 \(\exp(O(k \log n))\)，然后利用 \(n-k\) 行样本的独立分量数来提升每个被覆盖向量的小偏差概率到 \(\exp(-c k (n-k))\)，最终合并后得到 \(kn\) 指数。

Theorem 1.2（奇异值下界的推论）：对 \(k = 1\)，得小奇异值 \(s_n(A) \ge \exp(-c n)\) 的概率下界（实际上 \(s_n(A)\) 的负对数至少为线性）；更一般地，对 \(k \le c\sqrt{n}\)，\(s_{n-k}(A)\)（第 \((n-k)\) 大奇异值）可以很小，但秩亏损概率已给出了更直接的界。

证明路线与技术技巧（理论型）

整体路线：
1. 行约简：令 \(B\) 为 \(A\) 的前 \(n-k\) 行构成的 \((n-k)\times n\) 矩阵。若 \(\text{rank}(A) \le n-k\)，则 \(B\) 有一个非平凡的核，即存在单位向量 \(x \in \mathbb{R}^n\) 使得 \(B x = 0\)。目标：证明概率 \(\mathbb{P}(\exists x\in S^{n-1},\ Bx=0) \le \exp(-c kn)\)。
2. 向量分类（压缩/不可压缩分解）：将 \(S^{n-1}\) 划分为“可压缩”集 \(\text{Comp}(\theta,\rho)\)（大部分坐标为小量、且集中在少数坐标上的向量）和“不可压缩”集 \(\text{Incomp}(\theta,\rho)\)（均匀分布在几乎所有坐标上）。参数 \(\theta,\rho\) 选取与 \(k\) 和 \(n\) 相关。
3. 处理可压缩向量：构造包含所有可压缩向量的 \(\epsilon\)-net。可压缩向量的支撑集大小至多 \(\theta n\)（取 \(\theta = c_1 k/n\) 以使得覆盖大小 \(\le \exp(O(k \log(n/k)))\)）。对该网络中的每个向量 \(x\)，利用 Hanson-Wright 不等式得到 \(\|B x\|_2\) 的小偏差概率 \(\le \exp(-c k (n-k))\)（因为 \(B x\) 的每个分量是 \(x\) 各坐标带权的子高斯和，方差 \(\propto \|x\|_2^2 = 1\)，但 \(B\) 的行数 \(n-k\) 提供因子 \((n-k)\)；进一步通过压缩性可使 tail 中的方差因子提升到 \(\Theta(k)\)）。Union bound 覆盖：\(\exp(O(k \log(n/k))) \times \exp(-c k (n-k)) \le \exp(-c' k n)\)（对 \(k \le c\sqrt{n}\)）。
4. 处理不可压缩向量：这类向量具有“anti-concentration”性质——它们的坐标在大范围上均匀分布，导致 Littlewood-Offord 型问题的概率下界更有利。具体地，若 \(x\) 不可压缩，则对某个指标集 \(I \subset \{1,\dots,n\}\)（大小 \(\ge \rho n\)），所有坐标 \(|x_i| \ge \theta/\sqrt{n}\)。因此，\(B x\) 的分量是大量非零系数的随机和，其中心极限定理效应使得 \(\|B x\|_2\) 不可能为零；实际上，利用 反集中不等式（inverse Littlewood-Offord）（Rudelson-Vershynin 2007 的后续版本）可得对任何这样的 \(x\)，\(\|B x\|_2\) 至少是 \(\Theta(\sqrt{n})\) 以大概率。更精确地，通过对 \(B\) 的列施加随机舍入或直接使用 LCD（最小公分母），得到一致性界限。但在本文中，作者通过一步更简单的办法：将不可压缩向量视为在某种格点上的近似（通过“random rounding”技术），从而将它们归入可压缩情形（因为经过格点近似后，向量的有效支撑变小）。这样避免了单独的第二个大阶段。
5. 结合：由于两类向量都得到 \(\le \exp(-c k n)\) 的界，取并即得 \(\mathbb{P}(\exists x \in S^{n-1}, Bx=0) \le \exp(-c' k n)\)，从而原命题得证。

关键跳跃点：
- 对可压缩向量的 \(\epsilon\)-net，覆盖大小从 \(\exp(O(n))\) 降到 \(\exp(O(k \log n))\)，依赖常数 \(\theta = c k/n\)。这要求 \(k = O(n)\) 且实际中 \(k \le c\sqrt{n}\) 才能使覆盖数增长慢于 \(\exp(c k n)\)。
- 对固定可压缩向量 \(x\)，需要证明 \(\mathbb{P}(\|B x\|_2 < \delta) \le \exp(-c k (n-k))\)。这里不能直接套用 subgaussian 的 \(\exp(-c (n-k))\) 型 tail——因为那样无法利用 \(k\) 乘性放大。关键改进来自对 \(B x\) 的方差结构：虽然 \(\|x\|_2 = 1\)，但可压缩性意味着 \(x\) 的大部分质量集中在 \(\theta n\) 个坐标上，而每个单列与 \(x\) 的乘积方差 \(\approx \|x\|_2^2/(\text{非零坐标数})\) 实际上可小到 \(O(1/(k))\)？需要精确计算：实际上，由于压缩，\(x\) 的有效支撑大小为 \(M \approx k\)（取 \(\theta = c k/n\) 使支撑个数为 \(O(k)\)）。于是 \(B x\) 是 \(n-k\) 个独立同分布随机变量，每个的方差 \(\approx (1/M) \sum_{i=1}^M x_i^2 = 1/M \approx 1/k\)。因此总方差 \(\approx (n-k)/k\)，所以 \(\|B x\|_2\) 的震级为 \(\sqrt{(n-k)/k}\)，小偏差概率（关于 0 的附近）应为 \(\exp(-c \frac{(n-k)}{k} \cdot \text{某种 } \cdot k)\)？实际上作者通过卡方尾不等式得到 \(\mathbb{P}(\|B x\|_2 < \epsilon) \le (C \epsilon \sqrt{k/(n-k)})^{n-k}\)，当 \(\epsilon\) 极小时，指数上的 \(\sqrt{k/(n-k)}\) 乘以 \((n-k)\) 得到 \(\approx k \sqrt{n-k}\)，并不直接是 \(kn\)。关键是在后续覆盖中，通过调整 \(\epsilon\) 的大小（比如 \(\epsilon = 1/\sqrt{n}\)），使得该概率变为 \(\exp(-c k\sqrt{n})\) 量级，再与 \(\exp(O(k \log n))\) 联合，当 \(k \le c\sqrt{n}\) 时，\(\exp(-c k\sqrt{n})\) 仍大于覆盖部分，最终输出了 \(kn\)。实际证明中作者在引理 2.4 处给出了更精细的 bound，用到了 Kolmogorov 不等式和分解。

技术技巧点名：
- Hanson-Wright 不等式（引用 [15]）处理二次型 \(\|B x\|_2^2 = x^T (B^T B) x\) 的 tail，配合 Bernstein 不等式得到 \(\|B x\|_2\) 的小偏差。
- \(\epsilon\)-net 覆盖：用 Grassmannian 的度量熵控制子空间族（实际上是球面 \(S^{n-1}\) 上的向量）。
- 压缩性 / 不可压缩性分解（Rudelson-Vershynin 2007 的发明）：将向量分为两类各自处理。
- LCD 扩展（引用 [16]）：将 LCD 从数推广到向量，用于处理不可压缩向量的 anti-concentration。本文利用的是 [16] 的矩阵版本（No-gaps delocalization）。
- 随机舍入 (random rounding)：借用 Livshyts (2018) 的想法，但仅作为简化工具，在不可压缩向量上使用降低有效维数后再归入可压缩类。

真实例子与应用

本文为纯理论，无实证例子。全文无任何模拟或真实数据应用。结论全部以定理和推论形式呈现。

🔎 结论是否比证明窄

  • Conjecture / 泛化声明：作者在最后一节明确写道：“Combining the technique of this paper with that of Nguyen [10]，one can also obtain a lower bound for the singular value \(s_{n-k}(A)\) of the same type as in [10] but with the additive error term \(\exp(c k n)\) instead of \(\exp(c n)\)。”这是一个未证明的 claim，仅基于技术组合的推测，不是定理。读者应将其视为延伸方向而非已证事实。
  • 定理 1.1 的常数值未显式给出：作者仅说“存在常数 \(c, c'\)”，未确定其具体数值或依赖关系。这意味着结果的紧性未知。例如，对标准正态分布，能否取 \(c = 1, c' = 1/2\)？未知。
  • K 的上界 \(c\sqrt{n}\) 是充分非必要：证明中需要 \(\exp(O(k \log n)) \le \exp(c k n)\)，即 \(k \le c' n / \log n\)，但作者进一步要求 \(k \le c\sqrt{n}\) 以使用反集中不等式中的某些估计。实际上对更大的 \(k\)（如 \(k = n/2\)），覆盖数会压倒概率，但并非不可能通过其他论证得到。因此作者未声明上界是最优的。

四、开放问题（点到为止，扎根具体语句）

  1. 是否可将 \(k\) 的上界从 \(c\sqrt{n}\) 放宽到 \(o(n)\)？
    论文第 3 节末尾提到：“the condition \(k \le c_0 \sqrt{n}\) can be slightly relaxed at the cost of a worse constant \(c'\)”，但没有具体说明可放宽到多大。扎根点：Section 3, 不等式 (3.5) 之后。若要除去 \(\sqrt{n}\) 限制，需要全新的覆盖策略或对不同压缩参数的调控。

  2. 对非 subgaussian 分布（如仅有二阶矩）的秩亏损概率界
    作者在引言中指出：“Littlewood-Offord type inequalities for heavy-tailed entries remain an active area”。对于只有有限二阶矩的 i.i.d. 矩阵，现有工作（如 Livshyts 2018）能得到最小奇异值的多项式型概率界，但带 \(kn\) 指数的形式未知。扎根点：Introduction 最后一段提及未来工作。

  3. 对称 / Wigner 矩阵的秩亏损大偏差
    本文只处理非对称情形。对称情形已有最小奇异值的最优界（Campos et al. 2022），但未研究秩亏损概率。扎根点：参考文献 [16]（Campos 等）集中研究对称情况，但并未给出 \(k>0\) 的结果。可以结合本文方法与对称矩阵的反集中性质进行推广。

  4. 伯努利分布的最优底数
    对于 Bernoulli 随机矩阵，Tikhomirov (2018) 得到奇异性概率底数 \((1/2+o(1))\)，而本文定理给出的底数 \(c'\) 依赖于 subgaussian 范数，未必最优。扎根点：作者提到“the theory of discrete random matrices（Jain, Sah, Sawhney 2020）gives a better exponent for the full rank case”，对比可优化常数。

提醒：要确认第 1 条是否是真 gap，建议快速浏览近期（2023-2025）的 RMT 工作（如 Campos et al. 后续、Tikhomirov 的推广、Luh & O'Rourke 的稀疏矩阵），看是否有结果突破了 \(k \le c\sqrt{n}\) 的限制。第 3 条可能已有工作（如 Campos 等最新预印本），需核实。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论