Return to Question

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_2\mathbb B^k \subseteq Z\mathbb B^n$, where $c_2\mathbb B^k$ is the ball of radius $c_2$ in $\mathbb R^k$ and $Z\mathbb B^n := \{Zv \mid v \in \mathbb B^n\}$.

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.

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

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

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_2\mathbb B^k \subseteq Z\mathbb B^n$, where $c_2\mathbb B^k$ is the ball of radius $c_2$ in $\mathbb R^k$ and $Z\mathbb 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$ ?

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_2\mathbb B^k \subseteq Z\mathbb B^n$, where $c_2\mathbb B^k$ is the ball of radius $c_2$ in $\mathbb R^k$ and $Z\mathbb B^n := \{Zv \mid v \in \mathbb B^n\}$.

Special case of vectors. In the particular case where $m=1$, we note that the vector $X \in \mathbb R^n$ is $(c_1,c_2)$-incompressible iff $c_1 = 1$ and $\|X\|_2 \ge c_2$.

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.

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

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

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_2\mathbb B^k \subseteq Z\mathbb B^n$, where $c_2\mathbb B^k$ is the ball of radius $c_2$ in $\mathbb R^k$ and $Z\mathbb B^n := \{Zv \mid v \in \mathbb B^n\}$.

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.

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

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

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

Fix $\delta \in (0, 1)$ once and for all.

Q: Is it possible to find universal constants $c_1 > 0$ and $c_2 > 0$ (depending only on $\delta$) such that the following phenomenon holds ?

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. Finally, denote by $c_2\mathbb B^k$ the ball of radius $c_2$ in $\mathbb R^k$.

With high probability, 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 this probability be as a function of $n$ and $\delta$ ?

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_2\mathbb B^k \subseteq Z\mathbb B^n$, where $c_2\mathbb B^k$ is the ball of radius $c_2$ in $\mathbb R^k$ and $Z\mathbb B^n := \{Zv \mid v \in \mathbb B^n\}$.

Special case of vectors. In the particular case where $m=1$, we note that the vector $X \in \mathbb R^n$ is $(c_1,c_2)$-incompressible iff $c_1 = 1$ and $\|X\|_2 \ge c_2$.

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.

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

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