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.

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

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .