4
$\begingroup$

Let $X \in \mathbb{R}^{n \times d}$ be a random matrix with independent elements $N(0, 1)$ and let $\mathbf{1}$ be an n-vector of ones. Assume that $d \asymp n^\alpha$ for some $\alpha > 0$. I would like to find a bound on $ \|(n^{-1}X'X)^{-1}n^{-1}X'\mathbf{1}\|_{\infty} $ that holds with probability $1-o(1)$.

Simulations suggest that the bound should look like ${\cal O}(\sqrt{\frac{d}{n}})$ (modulo logarithmic factors in d and n), but I have problems proving that.

Below are a few approaches that I have tried, but am not sure how to proceed with them.

Question 1: Using standard Gaussian tail bounds, we have that $\|n^{-1}X'\mathbf{1}\|_{\infty} \leq \sqrt{\frac{2\log(d\log(n))}{n}}$ with probability $1-o(n)$. Is there a way to condition on the event $\{\|n^{-1}X'X - I\|_{\rm op} \leq c_1\sqrt{\frac{d}{n}}\}$ and analyze $\|n^{-1}X'\mathbf{1}\|_{\infty}$ on it? That is, how does distribution of $\|n^{-1}X'\mathbf{1}\|_{\infty}$ change once we condition on $\{\|n^{-1}X'X - I\|_{\rm op} \leq c_1\sqrt{\frac{d}{n}}\}$?

Question 2: Let $X = USV'$ be the SVD decomposition of $X$. Then $(n^{-1}X'X)^{-1}n^{-1}X'\mathbf{1} = VS^{-1}U'\mathbf{1}$. Can I assume without loss of generality that $V = I$, that is, the matrix $V$ is identity, since the distribution of $X$ is rotationally invariant?

Question 3: This is related to previous question. How does the distribution of $X'\mathbf{1}$ change once we condition on $S$.

1 Answers 1

2

I will assume that $d \asymp n^\alpha$ with $\alpha < 1$, so that $d < n$ asymptotically. (If $\alpha > 1$, then $X'X$ is not invertible for $n \ge 2$, and you have to be more careful in stating what you mean.) Then the singular values of $X$ are in $ (\sqrt{n} - \sqrt{d} -t,\sqrt{n} + \sqrt{d} +t) $ with prob. at least $1 - 2\exp(-t^2/2)$. It follows that the least singular value of $\frac1{\sqrt{n}} X$ is bounded below by $1-C \sqrt{d/n}$ w.h.p. Then, the largest singular value of $(\frac1n X'X)^{-1}$, that is, its operator norm, is bounded above by $1/(1 -C \sqrt{d/n})^2 = 1 +C' \sqrt{d/n}$ for $n$ large enough.

On the other hand as you mentioned $\| \frac{1}{n} X'1\|_\infty \le C'' \sqrt{\frac{\log d}{n}}$ w.h.p. and $\| \cdot\|_2 \le \sqrt{d} \| \cdot\|_\infty $ over $\mathbb{R}^d$. Putting the pieces together, \begin{align*} \| (\frac1n X'X)^{-1} \frac{1}{n} X'1\|_\infty &\le \| (\frac1n X'X)^{-1} \frac{1}{n} X'1\|_2 \\ &\le \| (\frac1n X'X)^{-1} \|_{\text{op}} \;\| \frac{1}{n} X'1\|_2 \\ &\le (1 + C'\sqrt{\frac{d}{n}})\; \sqrt{d} \| \frac{1}{n} X'1\|_\infty\\ &\le(1 + C'\sqrt{\frac{d}{n}})\; \sqrt{d} \;C''\sqrt{\frac{\log d}{n}} \\ &\le C'''\sqrt{\frac{d \log d}{n}} \end{align*} for large $n$, w.h.p.

Please check, as I may have made a mistake.

  • 0
    Thanks. The analysis looks correct to me. I wonder if a more tight analysis could be performed, since first you upper bound linf norm with l2 norm and then l2 norm with linf norm. That is, it would be interesting if one could directly bound (linf, linf)-matrix norm, as opposed to using the operator norm.2012-06-12