# 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$$ ?

## Related Questions

### Rings whose Frobenius is flat

0  Asked on December 30, 2020 by anon1432

### $ell^1$-norm of eigenvectors of Erdős-Renyi Graphs

1  Asked on December 30, 2020 by stefan-steinerberger

### The problems of global asymptotic freeness

1  Asked on December 29, 2020 by iliyo

### What OEIS sequence is this?

1  Asked on December 29, 2020 by a-z

### Reference for the rectifiablity of the boundary hypersurface of convex open set

1  Asked on December 28, 2020

### Tannakian group of Galois representations coming from geometry

0  Asked on December 27, 2020 by smn

### Why there is no 3-category or tricategory of bicategories?

1  Asked on December 27, 2020 by lolman

### Analytically controlling sizes in modular arithmetic to demonstrate Dirichlet pigeonhole application

1  Asked on December 27, 2020

### “Weakly” nuclear operators (terminology)

0  Asked on December 26, 2020 by pea

### holomorphy in infinite dimensions (holomorphic families of operators)

2  Asked on December 26, 2020 by andr-henriques

### Max weighted matching where edge weight depends on the matching

2  Asked on December 25, 2020

### Faltings’ height theorem for isogenies over finite fields

0  Asked on December 21, 2020 by asvin

### Probability of positivity of rational solutions to a diophantine system?

0  Asked on December 21, 2020 by vs

### On sup over boundaries of Sobolev functions

0  Asked on December 20, 2020 by yongmin-park

### On weaker forms of the abc conjecture from the theory of Hölder and logarithmic means

1  Asked on December 18, 2020 by user142929

### Set of points with a unique closest point in a compact set

2  Asked on December 18, 2020 by piotr-hajlasz

### Complex $2$ manifold $M$ with a given real 2 dimensional submanifold which meets all complex limit cycles of foliations of $M$

0  Asked on December 17, 2020 by ali-taghavi

### Rigorous multivariate differentiation of integral with moving boundaries (Leibniz integral rule)

1  Asked on December 17, 2020 by amir-sagiv

### Closed form of the sum $sum_{rge2}frac{zeta(r)}{r^2}$

0  Asked on December 15, 2020 by epic_math