这个工具到底该用什么，说实话，我也只有一些粗浅的想法，我想的是使用markov不等式估计概率，这主要是利用到联合高斯分布的性质是服从联合高斯分布的两个独立向量的和，依然服从联合高斯分布，但这之后，我并不确定高斯分布替换成均匀分布或者伯努利分布之后还能否得到多项式界......”

“另外，这道题的难点主要在于如何估计这个随机矩阵的最小奇异值，而想要估计随机矩阵的最小奇异值，最主要的难点是如何突破随机矩阵理论中元素之间的独立性，如果无法解决这一步，这道题的证明也就无从谈起。”

随机矩阵理论起源于对物理模型的研究，人们在早期实验中发现，一些大型随机矩阵的特征值与奇异值的分布常常趋近于某些特定的分布，并由此提出了如半圆律、圆律与 marchenko-pastur律之类关于极限分布的定律。

这些定律的假设和结论类似于经典概率论里的中心极限定理（即大量相互独立的随机数之和的分布常常趋近于正态分布），这需要假设矩阵元素除了特定结构以外相互独立，再让维度趋于无穷。

尽管如此，极限毕竟是极限，从不等式估计的角度来看，用起来还是不太顺手的。

大约从上世纪 80年代末开始，人们开始研究非渐进意义下的奇异值的估计，其中最核心的部分就是对于最小奇异值的估计。

随机矩阵的发展也从一开始首先处理了独立同分布的矩阵元素服从高斯分布的情形，逐渐放松要求，开始不要求高斯分布，不要求同分布，并且得到了越来越精准的估计。

但这其中最难放松的条件依旧是独立性，这要求，一是改成要求矩阵的各行相互独立。

二是要求矩阵有额外的结构，如对称性，而除此以外相互独立。

三是要求矩阵元素之间的相关性随在矩阵中的位置的距离而指数级衰减......

“从萧