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

MathOverflow Asked on January 1, 2022

Context. Studing a problem in machine-learning, I’m led to consider the following problem in RMT…

Definition. Given positive integers $$m$$ and $$n$$ and positive real numbers $$c_1$$ and $$c_2$$, let’s say an $$m$$-by-$$n$$ real matrix $$X$$ is $$(c_1,c_2)$$-incrompressible if every submatrix of $$Z$$ with $$k ge c_1 m$$ rows and $$n$$ columns satisfies $$c_2mathbb B^k subseteq Zmathbb B^n$$, where $$c_2mathbb B^k$$ is the ball of radius $$c_2$$ in $$mathbb R^k$$ and $$Zmathbb B^n := {Zv mid v in mathbb B^n}$$.

Question. Is the definition somehow linked to the classical "restricted isometry property" ?

An answer to this the above question would allow me to directly tap into the vast RMT literature, for the purposes of attacking my subsequent questions (see below).

Special case when $$c_1=1$$.
In the particular case where $$c_1=1$$, we note that $$X$$ is $$(1,c_2)$$-incompressible iff its smallest singular value is $$c_2$$ or greater.

Now, fix $$delta in (0, 1)$$ once and for all.

Question. Do there exist universal constants $$c_1 > 0$$ and $$c_2 > 0$$ (depending only on $$delta$$) such that the following phenomenon holds ?

The phenomenon. Let $$m$$ and $$n$$ be positive integers with $$m le delta n$$ and $$n$$ large, and let $$k ge c_1 m$$. Let $$X$$ an $$m$$-by-$$n$$ random real matrix with iid $$N(0,1)$$ entries.

Question. With high probability, $$X$$ is $$(c_1,c_2)$$-incompressible!

Also, how large can this probability be as a function of $$n$$ and $$delta$$ ?