Skip to main content
3 of 5
removed capitals, added tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

Probabilistic lower bound on largest singular value of matrices

I have a distribution $\mathcal{D}$ that spits out vectors in $\{-1, 1\}^N$. Suppose I have a sample of $H$ of these vectors which I arrange into a matrix $M$ of the form $H \times N$.

Consider the eigenvalues of $\frac{MM^T}{NH}$. Note that each row sum is at most $1$. Thus, the maximum eigenvalue is at most $1$.

Is there some way of defining a measure of complexity of $\mathcal{D}$ that lets me say with high probability the maximum eigenvalue is only $\varepsilon$ away from 1? Hopefully the lower the complexity, the closer it is to one. However, increasing $N$ should bring it closer to 1.

Halbort
  • 1.1k
  • 1
  • 7
  • 20