Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted
+100

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.

share|improve this answer
    
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. –  mkolar Jun 12 '12 at 22:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.