# Bounding $\|(X'X)^{-1}X'\mathbf{1}\|_{\infty}$ in probability

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$.

-

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.