0
$\begingroup$

Let $X = (x_{ij}) \in \mathbb{R}^{n \times p}$ be a matrix with independent $N(0,1)$ entries.

We know that $\max_j x_{ij} < \sqrt{2\log(p/\delta)}$ with probability at least $1-\delta$.

I would like to obtain a lower bound for $\min_i (\max_j x_{ij})$ that holds with probability at least $1-\delta$. Could somebody point to a relevant reference please?

2 Answers 2

1

You know that

$\Pr(\max_j x_{ij} \le k) = \Phi(k)^p$

so

$\Pr(\max_j x_{ij} \gt k) = 1 - \Phi(k)^p$

so

$\Pr(\min_i (\max_j x_{ij}) \gt k) = \left(1 - \Phi(k)^p\right)^n $

so

$\Pr(\min_i (\max_j x_{ij}) \le k) = 1- \left(1 - \Phi(k)^p\right)^n $

and if this is is equal to $1-\delta$ then

$k = \Phi^{-1}\left( (1- \delta^{\frac{1}{n}})^{\frac{1}{p}} \right)$

  • 0
    @Aditya: Yes - thank you2012-05-17
0

You might try Gordon's inequality, which is a sort of comparison inequality for Gaussian processes. Here is a lecture note:

http://www-personal.umich.edu/~romanv/teaching/2006-07/280/lec11.pdf

Not sure if it gives the result you want. The general reference for these types of inequalities is Chapter 3 of Probability in Banach Spaces by Ledoux and Talagrand. Also, take a look at: http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf