Skip to main content
1 of 7
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Given a large random matrix, how to prove that every large submatrix whose range contains a large ball?

Studing a problem in machine-learning, I'm led to consider the following problem.

Q: Is it possible to find universal constants $c_1 > 0$ and $c_2 > 0$ such that the following phenomenon holds ?

Phenomenon. Let $m$ and $n$ be large positive integers and let $k \ge c_1 m$. Let $X$ an $m$-by-$n$ random real matrix with iid $N(0,1)$ entries. Finally, denote by $c_2\mathbb B^k := \mathbb B^k(c_2)$ the ball of radius $c_2$ in $\mathbb R^k$.

With high probability $p(n,m)$, every $k$-by-$n$ submatrix $Z$ of $X$ verifies $$ c_2\mathbb B^k \subseteq Z\mathbb B^{n}:= \{Zv \mid v \in \mathbb B^n\}. $$

Also, how large can the $p(n,m)$ probability be ?

dohmatob
  • 6.9k
  • 1
  • 18
  • 76