1
$\begingroup$

Consider the distribution given by taking the top singular vector of a matrix whose entries are equally likely to be +1 or -1. This is not well-defined for matrices where the subspace achieving the top singular value is >1-dimensional, but we can ignore this case since it occurs with negligible probability.

Can we say anything obvious about how this distribution compares to the uniform distribution on unit norm vectors (that is, the distribution on the top singular vector of an iid Gaussian matrix); say, that the support of the distribution forms some $\varepsilon$-net of the general space, or that no matter what direction I choose, the probability that I pull a singular vector that is close to that direction is about uniform?

Essentially I'm looking for some discrete analogue of rotational invariance, and I want to determine whether this distribution satisfies such a property.

Sorry if this is well-known, but I would appreciate being pointed to the relevant literature.

$\endgroup$
3
  • $\begingroup$ It's not clear to me how you fix a direction and then send the dimension to infinity; the unit spheres don't seem nested in any obvious way, and you have to deal with concentration of measure for large $n$. Ignoring that, if I understand "singular vector" correctly (you want the $x$ that maximizes $\|Ax\|$), then something close to an $e_j$ seems to have a better chance of working than, say, $(1,1, \ldots , 1)/\sqrt{n}$. $\endgroup$ Dec 3, 2017 at 7:19
  • $\begingroup$ Your point makes sense, I need a better property to consider here. What's your intuition behind saying $e_j$ has a better chance than $(1,\ldots,1)/\sqrt{n}$? The norm of $\|Ae_j\|$ is always fixed at $\sqrt{n}$, so theoretically it should never be the top singular vector (except for the case where all singular values are the same). The ones vector achieves the top singular value for the all-ones matrix, so it should have a higher probability. $\endgroup$
    – Ewin
    Dec 3, 2017 at 22:37
  • $\begingroup$ Yes, exactly $e_j$ is not likely to work. I was just thinking that $A^*A_{jj}=n$, while most of the other matrix elements will likely be quite a bit smaller due to cancellations, so $x=e_j$ may not be such a terrible choice to make $x^*A^*Ax$ large. $\endgroup$ Dec 3, 2017 at 23:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.