Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $Y=X^\top W$ , with $X, W \in \mathbb{R}^{d \times d}$ are random matrices with standard normal entries. Let $\lambda_j$ be the $j^{th}$ singular value of $Y$. Is there a way to bound the tail probability of the $L_2$ norm of the top $k$ singular values of $Y$, i.e. $ P\Big(\sqrt{ \lambda_1^2(Y)+ \lambda_2^2(Y) + ... \lambda_k^2(Y)} > t \Big) \leq ? $ .

As a simple first try, I used $\sqrt{ \lambda_1^2(Y)+ \lambda_2^2(Y) + ... \lambda_K^2(Y)} \leq \sqrt{K}\lambda_1(Y)$ and used bounds for $\lambda_{max}$ of a matrix of the form of $Y$. But I need more tighter bounds and was wondering if there are other ways.

I would appreciate if you could let me know of any previous work done for this case that you might be aware of.

share|improve this question
1  
In what sense is the naive bound you suggest not good enough? –  ofer zeitouni Sep 8 '13 at 22:23
    
I was wondering if one could do better than $\sqrt{k}$ times the $\lambda_{max}$ –  Krishna Sep 9 '13 at 21:16
    
This is clear, but my question was, what is the relation of k and d (I assume $d$ is large)? Note that in the model you suggested, for k fixed this bound will be essentially optimal (i.e., up to $(1+o_d(1))$ from the truth) - I suspect so because I believe that the top singular value sticks to the edge of the limiting distribution of singular values. –  ofer zeitouni Sep 9 '13 at 23:21
    
I am interested in the regime when $d$ increases linearly in $k$ –  Krishna Sep 10 '13 at 2:55

1 Answer 1

In case $d$ increases linearly in $k$, say $k=\alpha d$, you can compute the limiting spectral measure of your matrix (you are dealing with the product of two wishart matrices, so you can compute the limit e.g. by computing moments, or better using free probability). Call the limit distribution $F$. Then the statistics you are after is $\sqrt{\int_{F^{-1}(\alpha)}^\infty x^2 dF(x)}$. If you want estimates on the error, you can use concentration inequalities for the spectral measure (since the top singular value concentrates as well).

share|improve this answer
    
thanks ofer, let me try this out. –  Krishna Sep 12 '13 at 16:34

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.