2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ In what sense is the naive bound you suggest not good enough? $\endgroup$ Sep 8 '13 at 22:23
  • $\begingroup$ I was wondering if one could do better than $\sqrt{k}$ times the $\lambda_{max}$ $\endgroup$
    – Kcafe
    Sep 9 '13 at 21:16
  • $\begingroup$ 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. $\endgroup$ Sep 9 '13 at 23:21
  • $\begingroup$ I am interested in the regime when $d$ increases linearly in $k$ $\endgroup$
    – Kcafe
    Sep 10 '13 at 2:55
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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