9 6 8 Restricted Isometry Constant For Gaussian Matrices

Let $\bf{X}$ be an $n \times p$ matrix:

(1)

\begin{align} {\bf{X}} = \begin{pmatrix} (X^{(1)})^T \\ \vdots \\ (X^{(n)})^T \end{pmatrix} \end{align}

where $\forall i \in 1, \ldots, n, \quad X^{(i)} \overset{i.i.d.} {\sim} \mathcal{N}_p(0,\Sigma)$.

For a linear span $V \subset \mathbb{R}^p$ and an $n \times p$ matrix $Z$, we introduce the notation

(2)

\begin{align} \lambda_V(Z) = \underset { v \in V \setminus \left\{ 0 \right\} } {\sup} \frac{n^{-1/2} \| Zv \| }{ \| v \| } \end{align}

1.

We define $Z := {\bf{X}} \Sigma^{-1/2}$
This defines each line of $Z$ as $(Z^{(i)})^T = (X^{(i)})^T \Sigma^{-1/2}$
Hence: $(Z^{(i)}) = (\Sigma^{-1/2})^T X^{(i)}$
According to lemma A.1, and since $(\Sigma^{-1/2})^T \Sigma (\Sigma^{-1/2})^T = I_p$ :
$\forall i \in 1, \dots, n, \quad Z^{(i)} \overset{i.i.d.} {\sim} \mathcal{N}(0, I_p)$
which means that the $Z_{ij}$ are i.i.d. with $\mathcal{N}(0, 1)$ Gaussian distribution.

2.

We write $\mathcal{M}$ for the set gathering all the subsets of $\left\{1,\ldots,n \right\}$. For $m \in \mathcal{M}$, we define $S_m$ as the linear space spanned by $\left\{ e_j : j \in \mathcal{M} \right\}$, where $e_1, \ldots, e_p$ is the canonical basis of $\mathbb{R}^p$. To each linear span $S_m$, we associate the linear span $V_m = \Sigma^{1/2} S_m$. We have, for a given $m$ :

(3)

\begin{align} \lambda_{V_m}(Z) &= \underset { v \in V_m \setminus \left\{ 0 \right\} } {\sup} \frac{n^{-1/2} \| Zv \| }{ \| v \| } \\ &= \underset { \beta \in S_m \setminus \left\{ 0 \right\} } {\sup} \frac{n^{-1/2} \| Z \Sigma^{1/2} \beta \| }{ \| \Sigma^{1/2} \beta \| } \end{align}

Hence,

(4)

\begin{align} \underset{m \in \mathcal{M}:|m|=d}{\sup} \lambda_{V_m}(Z) &= \underset { \beta : |\beta|_0=d } {\sup} \frac{n^{-1/2} \| Z \Sigma^{1/2} \beta \| }{ \| \Sigma^{1/2} \beta \| }\\ &= \underset { \beta : |\beta|_0=d } {\sup} \frac{n^{-1/2} \| \bf{X} \beta \| }{ \| \Sigma^{1/2} \beta \| } \end{align}

3.

In the following, we use any collection $V_1, \ldots, V_N$. Let $P_{V_i}$ be the orthogonal projector onto $V_i$.
For this question, we take $i\in\{1,\ldots,N\}$ fixed.
Since $\underset{x}{\sup} \frac{\|Ax\|}{\|x\|}$ defines a norm, and norms are 1-Lipschitz, we can use the Gaussian concentration inequality for the function $Z \mapsto \sqrt{n} \lambda_{V_i} (Z)$.
Thus, there exists a random variable $\xi$ such that:

(5)

\begin{align} \sqrt{n} \lambda_{V_i}(Z) \le \mathbb{E} \left[\sqrt{n} \lambda_{V_i}(Z) \right] + \sqrt{2\xi _i} \end{align}

We also know that

(6)

\begin{align} \sqrt{n} \lambda_{V_i}(Z) &= \underset { v \in {V_i} \setminus \left\{ 0 \right\} } {\sup} \frac{ \| Zv \| }{ \| v \| }\\ &= \underset { v \in {V_i} \setminus \left\{ 0 \right\} } {\sup} \frac{ \| ZP_{V_i}v \| }{ \| v \| }\\ &\le \underset { u \in \mathbb{R} \setminus \left\{ 0 \right\} } {\sup} \frac{ \| ZP_{V_i}u \| }{ \| u \| }\\ &\le \sigma_1(ZP_{V_i}) \end{align}

where $\sigma_1(ZP_{V_i})$ is the largest eigen value of $P_{V_i}$, and:

(7)

\begin{align} \mathbb{E}\left[\sigma_1(ZP_{V_i})\right]\le\sqrt{n} + \sqrt{d} \end{align}

so we finally get:

(8)

\begin{align} \lambda_{V_i}(Z) \le 1+\sqrt{\frac{d}{n}} + \sqrt{2\frac{\xi_i}{n}} \end{align}

4.

Similarly to Eq.(5), we can write a concentration inequality on the supremum. There exists an exponential random variable $\xi$ of parameter 1, such that:

(9)

\begin{align} \underset{i=1,\ldots,N}{\sup}\lambda_{V_i}(Z) &\le \mathbb{E}\left[ \underset{i=1,\ldots,N}{\sup} \lambda_{V_i}(Z) \right] + \sqrt{2\frac{\xi}{n}} \end{align}

Using Eq.(8):

(10)

\begin{align} \underset{i=1,\ldots,N}{\sup}\lambda_{V_i}(Z) &\le \mathbb{E}\left[ \underset{i=1,\ldots,N}{\sup} 1 + \sqrt{\frac{d}{n}} + \sqrt{2\frac{\xi_i}{n}} \right] + \sqrt{2\frac{\xi}{n}}\\ &\le 1 + \sqrt{\frac{d}{n}} + \mathbb{E}\left[ \underset{i=1,\ldots,N}{\max}\sqrt{2\frac{\xi_i}{n}} \right] + \sqrt{2\frac{\xi}{n}} \end{align}

5.

According Jensen's inequality, with the convex function $x \mapsto e^{sx}$:

(11)

\begin{align} \exp\left(s \mathbb{E} \left[ \sqrt{2\xi_i} \right] \right) &\le \mathbb{E} \left[ \exp\left(s \sqrt{2\xi_i} \right) \right]\\ \overset{N}{\underset{i=1}{\sum}} \exp\left(s \mathbb{E} \left[ \sqrt{2\xi_i} \right] \right) &\le \overset{N}{\underset{i=1}{\sum}} \mathbb{E} \left[ \exp\left(s \sqrt{2\xi_i} \right) \right]\\ \end{align}

Since $\exp\left(s \mathbb{E} \left[ \sqrt{2\xi_i} \right] \right) \ge 0$

(12)

\begin{align} \exp \left( s \mathbb{E} \left[ \underset{i=1,\ldots,N}{\max} \sqrt{2\xi_i} \right] \right) = \max_{i=1,\ldots,N}\exp \left( s \mathbb{E} \left[\sqrt{2\xi_i} \right] \right) \le \overset{N}{\underset{i=1}{\sum}} \exp\left(s \mathbb{E} \left[ \sqrt{2\xi_i} \right] \right) \end{align}

And finally:

(13)

\begin{align} \mathbb{E} \left[ \underset{i=1,\ldots,N}{\max} \sqrt{2\xi_i} \right] \le s^{-1} \log \left( \overset{N}{\underset{i=1}{\sum}} \mathbb{E} \left[ \exp\left(s \sqrt{2\xi_i} \right) \right] \right) \end{align}

6.

Rewriting the expectation:

(14)

\begin{align} \mathbb{E} \left[ e^{s\sqrt{2\xi}} \right] = \int_0^{\infty} e^{s\sqrt{2x}}e^{-x}dx \end{align}

Change of variables: $u=\sqrt{2x}$

(15)

\begin{align} \mathbb{E} \left[ e^{s\sqrt{2\xi_i}} \right] &= \int_0^{\infty} e^{su-u^2/2}udu \\ &= \int_0^{\infty} e^{-\frac{1}{2}(u-s)^2+\frac{s}{2}}udu \\ &= e^{\frac{s^2}{2}} \left( \int_0^{\infty}e^{-\frac{1}{2}(u-s)^2}(u-s)du+s\int_0^{\infty}e^{-\frac{1}{2}(u-s)^2}du \right) \\ &\le e^{\frac{s^2}{2}} \left( \int_0^{\infty}e^{-\frac{1}{2}(u-s)^2}(u-s)du+s\int_{-\infty}^{+\infty}e^{-\frac{1}{2}(u-s)^2}du \right) \\ &\le e^{\frac{s^2}{2}} \left( e^{\frac{-s^2}{2}} + s \sqrt{2\pi} \right) \\ \end{align}

And finally:

(16)

\begin{align} \mathbb{E} \left[ e^{s\sqrt{2\xi_i}} \right] \le s \sqrt{2\pi} e^{\frac{s^2}{2}} +1 \end{align}

7.

Using (13) in (16), we obtain:

(17)

\begin{align} \mathbb{E} \left[ \underset{i=1,\ldots,N}{\max} \sqrt{2\xi_i} \right] &\le s^{-1} \log \left( \overset{N}{\underset{i=1}{\sum}} \left( s \sqrt{2\pi} e^{\frac{s^2}{2}} +1 \right) \right) \\ &\le s^{-1} \log \left( N s \sqrt{2\pi} e^{\frac{s^2}{2}} +N \right) \end{align}

We choose $s=\sqrt{2 \log N}$:

(18)

\begin{align} \mathbb{E} \left[ \underset{i=1,\ldots,N}{\max} \sqrt{2\xi_i} \right] &\le \frac{1}{\sqrt{2 \log N}} \log \left( N \left( N \sqrt{4 \pi \log N} +1 \right) \right) \\ &\le \frac{1}{\sqrt{2 \log N}} \left[ 2 \log N + \log \left( \sqrt{4 \pi \log N} + \frac{1}{N} \right) \right] \\ &\le \sqrt{2 \log N} +\frac{1}{\sqrt{2 \log N}} \log \left( \frac{1}{N} + \sqrt{4\pi \log N} \right) \end{align}

We write $\delta_N := \frac{1}{\sqrt{2 \log N}} \log \left( \frac{1}{N} + \sqrt{4\pi \log N} \right)$
We then have:

(19)

\begin{align} \mathbb{E} \left[ \underset{i=1,\ldots,N}{\max} \sqrt{2\xi_i} \right] &\le \frac{1}{\sqrt{n}} \left( \sqrt{2 \log N} + \delta_N \right) \end{align}

Using this result in (10):

(20)

\begin{align} \underset{m \in \mathcal{M}:|m|=d}{\sup} \lambda_{V_m}(Z) \le 1+\frac{\sqrt{d}+\sqrt{2\log N} + \delta_N + \sqrt{2\xi}}{\sqrt{n}} \end{align}