Probability distribution of the infinity norm of a Gaussian vector

Question

Let $N \geq 1$ be an integer.

Let $X$ be a standard $\mathbb{R}^N$ Gaussian vector (all components are $\mathcal{N}(0, 1)$ and i. i. d.).

Let $A \in \mathcal{M}_N(\mathbb{R})$ be a deterministic matrix.

Thus, $AX$ is a Gaussian vector.

Let $\epsilon \in (0, 1)$.

I would like to simulate Gaussian vectors of the form $AX$ that mostly have a smaller infinity norm than $\epsilon$, with only controlling the infinity norm of the matrix $A$.

So the question is: how to limit $||A||_{\infty} = \underset{i, j}{\max} |A_{i, j}|$ so that with high confidence / probability (let's say 95%), I get $||AX||_{\infty} \leq \epsilon$ ?

I am looking for an answer like: take $A$ such that $||A||_{\infty} \leq f(\epsilon)$. The answer is quite easy in the $1$-dimensional case, I would like to generalize it, but haven't found any clear theorem addressing that.

Thanks a lot for your help!

Answer 1

For some $n$ ($1$, $2$ and all multiples of $4$ if you admit a certain conjecture; all powers of $2$ if you don't), we can find explicitely the best bound.

Notwithstanding this conjecture, we find for $f(\varepsilon)$ a rate of convergence of $\frac{1}{\sqrt{n\log (n)}}$, less conservative than $\frac{1}{n}$.

---

We will denote by $X_0$ a standardized normal law $\mathcal{N}(0,1)$ independent (jointly) from our variables.

Lemma 1: for all $\varepsilon>0, r>0$, $\min \limits_{A \in \mathcal{M}_n(\mathbb{R}),\ ||A||_{\infty} \le r} \mathbb{P}\big(||AX||_{\infty} \le \varepsilon\big) \ge \mathbb{P}\big(|X_0| \le \frac{\varepsilon}{\sqrt{n}r}\big)^n$

The proof if a direct application of the Gaussian correlation inequality.

Proof: let $A \in \mathcal{M}_n(\mathbb{R})$ with $||A||_{\infty} \le r$. Then, for $i \in [\![1,n]\!]$, the region defined by $\big|(Ax)_i\big| \le \varepsilon$ is convex and symmetric about the origin. Thus $\mathbb{P}\big(||AX||_{\infty} \le \varepsilon \big) \ge \prod \limits_{i=1}^n \mathbb{P}\big(|(AX)_i| \le \varepsilon\big)$. Also, $(AX)_i \sim \mathcal{N}\big(0, \sum \limits_{j=1}^n a_{i,j}^2\big)$, so $\mathbb{P}\big(|(AX)_i| \le \varepsilon\big) = \mathbb{P}\Big(|X_0| \le \varepsilon / \sqrt{\sum_{j=1}^n a_{i,j}^2}\Big) \ge \mathbb{P}\big(|X_0| \le \frac{\varepsilon}{\sqrt{n}r}\big)$ since $||A||_{\infty} \le r$.

$ $

What this lemma says, is that the matrices $A$ for which we have the lowest confidence are the ones with

• uncorrelated outputs for $AX$, so orthogonal lines for $A$

• coefficients which are close (in absolute value) to $||A||_{\infty}$

These two properties bring us to the next section: we can find matrices satisfying these conditions, and reaching the bound of lemma $1$.

---

A Hadamard matrix of order $n$ is a matrix $H_n \in \mathcal{M}_n(\mathbb{R})$ with coefficients $+1$ or $-1$, such that $HH^T = nI_n$. While the construction of Hadamard matrix of order $2^k$ is obvious, a stil standing conjecture is:

Conjecture: for $n=1,2$ or any multiple of $4$, there exists a Hamadard matrix or order $n$.

Now why were we talking about Hadamard matrices again? That is because they are the worst case matrices for your problem:

Lemma 2: given a Hadamard matrix $H_n$, for $A = rH_n$ the bound of lemma $1$ is reached: $$\min \limits_{A \in \mathcal{M}_n(\mathbb{R}),\ ||A||_{\infty} \le r} \mathbb{P}\big(||AX||_{\infty} \le \varepsilon\big) = \mathbb{P}\big(||rH_nX||_{\infty} \le \varepsilon\big) = \mathbb{P}\big(|X_0| \le \frac{\varepsilon}{\sqrt{n}r}\big)^n$$

Proof: let us denote $A = rH_n$. Since the rows of $H_n$ are orthogonal, the $(AX)_i$ are uncorrelated, and as $AX$ is a gaussian vector, the $(AX)_i$ are independent. Thus $\mathbb{P}\big(||AX||_{\infty} \le \varepsilon\big) = \prod \limits_{i=1}^n \mathbb{P}\big(|(AX)_i| \le \varepsilon\big)$. Last, the coefficients of $A$ are either $r$ or $-r$, so $(AX)_i \sim \mathcal{N}(0, nr^2)$, and thus $\mathbb{P}\big(||AX||_{\infty} \le \varepsilon\big) = \mathbb{P}\big(|X_0| \le \frac{\varepsilon}{\sqrt{n}r}\big)^n$.

---

Conclusion: for all $n$, you can take $$f(\varepsilon) = \frac{\varepsilon}{\sqrt{n} \cdot F^{-1}\big(\frac{1+\alpha^{1/n}}{2}\big)}$$

with $F$ the cdf of $X_0$, to get $||AX||_{\infty} \le \varepsilon$ for all $A$ with $||A||_{\infty} \le f(\varepsilon)$, with confidence level at least $\alpha$, and exactly $\alpha$ for those $n$ for which a Hadamard matrix exist.

Using the asymptotics of $F^{-1}$, as $n \to +\infty$ you can take $f(\varepsilon) = \frac{\varepsilon}{\sqrt{n \log\big(\frac{4n^2}{\log(\alpha)^2}\big)}}$.

---

Answer 2

I doubt, that there is an exact formula to do this (that is if we want exactly 95% confidence and not just at least 95% confidence). For instance consider the two matrices $$A=\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \quad , \quad B=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}.$$ These matrices satisfy $||A||_\infty = 1 =||B||_\infty$, but clearly $||Ax||_{\infty} \leq ||Bx||_\infty$, thus matrices of the form $B$ would give larger confidence intervals.

The alternative is to give an upper bound for $||AX||_\infty$, and then establish a rule that gives the desired result with at least 95% confidence. One possibility is to use that

$$||AX||_\infty^2 \leq ||AX||_2^2 \leq n^2||A||_\infty^2||X||_2^2$$ so we can say that $$\mathbb{P}(||AX||_\infty < \epsilon) \geq \mathbb{P}(n^2||A||_\infty^2||X||_2^2 < \epsilon^2) = \mathbb{P}(||X||_2^2 < \frac{\epsilon^2}{n^2||A||_\infty^2})$$ But since $||X||_2^2$ is a sum of squared $i.i.d.$ $N(0,1)$ variables it has a $\chi^2$ distribution with $n$ degrees of freedom, and thus in order to get at least 95% confidence, we could choose $\frac{\epsilon}{n^2||A||_\infty^2}$ to be the $0.95$'th quantile of the $\chi^2(n)$ distribution. That is we require $||A||_\infty^2=\frac{\epsilon^2}{n^2 q}$, where $q$ is the said quantile so you could choose your function $f$ as $$f(\epsilon)= \frac{\epsilon}{n \sqrt{q}}$$

Another possibly better bound would be $||AX||_\infty \leq n ||A||_\infty ||X||_\infty$, but this requires that we know the distribution of $||X||_\infty$, which is a bit more complicated but possible.