Thursday, 10 September 2009

Question about "wide" random matrices

Let $A in mathbb{R}^{m times n}$ be a random matrix with i.i.d. entries (the distribution is not important), where $m < n$ (i.e. $A$ is a "wide" matrix). I would like a lower bound on
$$
phi(A) triangleq min_x frac{lVert Ax rVert}{lVert x rVert}
$$
that holds with high probability (apologies if the notation $phi(A)$ conflicts with any established usage).



When $m geq n$, evidently $phi(A) = sigma_{min}(A)$, the least singular value of $A$ (although I am not certain why this is true). Of course the distribution of the least singular value of a random matrix has been well-studied.



But when $m < n$, it seems that $phi(A) neq sigma_{min}(A)$ in general. For example, if $m = 1$ and $n > 1$, then $phi(A) = 0$ (just choose $x$ to be orthogonal to the vector $A$), but $sigma_{min}(A)$ is the Euclidean norm of the vector $A$, which usually will not be $0$.

No comments:

Post a Comment