Skip to main content
1 of 13
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

It looks like all the previous answers (including mine) are quite off by a huge margin, if the vector $a=(a_1,\ldots,a_n)$ is somewhat dense in the sense that $\|a\|_1/\|a\|_\infty$ is substantially larger than $1$. For example, if $a_i=1/n$ for all $i$, then we would expect to have the upper-bound to be of orde $\epsilon^{\Omega(n)}$, and not $\epsilon^{1/2}$. See Fact 2.1 of this blogpost.

In this post, I will provide an upper-bound which has somewhat optimal dependence on $a$.*


Given a random vector $Y$ in Euclidean $\mathbb R^m$, its concentration function is defined by setting, for any $\epsilon \ge 0$,

$$ \mathcal L(Y,\epsilon) := \sup_{y \in \mathbb R^m}L_y(Y,\epsilon),\text{ where }L_y(Y, \epsilon) := \mathbb P(\|Y-y\|_2 \le \epsilon\|A\|_{HS}). $$

Now, let $A$ be a deterministic $m \times n$ matrix and let $X$ be a random vector in $\mathbb R^n$ with independent components verifying $\max_{1 \le i \le n}\mathcal L(X_i,\epsilon) \le \ell(\epsilon)$. It is well-known (e.g see Theorem 1.5 of this paper by M. Rudelson) that for any $\delta \in (0,1)$, there exists a positive constant $C_\delta$ such that $$ \mathcal L(AX,\epsilon) \le (C_\delta \ell(\epsilon))^{(1-\delta)r(A)}, $$ where $r(A) := \|A\|_{HS}/\|A\|_{op} \ge 1$. In particular, if the $X_i$'s have standard normal distribution, then we may take $\ell(\epsilon)=\epsilon$, and get for any $\epsilon \ge 0$ and $\delta \in (0,1)$, $$ \mathcal L(AX,\epsilon) \le (C_\delta \epsilon)^{(1-\delta)r(A)}. $$

In particular, taking $A$ to be a diagonal matrix $\mbox{diag}(\sqrt{a_1},\ldots,\sqrt{a_n})$, we have

$$ \begin{split} \mathbb P(\sum_{i=1}^n a_i X_i^2 \le \epsilon \sum_{i=1}^n a_i) &= \mathbb P(\|AX\| \le \|A\|_{HS}) \le \mathcal L(AX,\epsilon) \le (C_\delta \epsilon)^{(1-\delta)r(A)}\\ & = (C_\delta \epsilon)^{(1-\delta)r(A)} = (C_\delta \epsilon)^{(1-\delta)r(a)}, \end{split} $$ with $r(a) = \sqrt{\|a\|_1 / \|a\|_\infty} \ge 1$. As a sanity check, if $a_i=1/n$ for all $i$, then $r(a) = n$, and our upper-bound has the right order in $\epsilon$, namely $\epsilon^{\Omega(n)}$.

dohmatob
  • 6.9k
  • 1
  • 18
  • 76