Question about "wide" random matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:38:45Z http://mathoverflow.net/feeds/question/37581 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37581/question-about-wide-random-matrices Question about "wide" random matrices umar 2010-09-03T05:27:44Z 2010-09-03T20:33:47Z <p>Let $A \in \mathbb{R}^{m \times n}$ be a random matrix with i.i.d. entries (the distribution is not important), where $m &lt; 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).</p> <p>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.</p> <p>But when $m &lt; 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$.</p> http://mathoverflow.net/questions/37581/question-about-wide-random-matrices/37600#37600 Answer by Bob Durrant for Question about "wide" random matrices Bob Durrant 2010-09-03T11:21:06Z 2010-09-03T11:29:33Z <p>These very useful notes will probably be of interest to you: <a href="http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf" rel="nofollow">http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf</a> starting at page 7.</p> http://mathoverflow.net/questions/37581/question-about-wide-random-matrices/37659#37659 Answer by umar for Question about "wide" random matrices umar 2010-09-03T20:09:02Z 2010-09-03T20:33:47Z <p>I spoke to someone locally, and we think the issue is which convention is used to define the singular values of a matrix. If one defines the singular values of a matrix $A$ to be the eigenvalues of the matrix $$\sqrt{A^TA}$$ then if $A$ is $m \times n$ with $m &lt; n$ we have $\sigma_{\min}(A) = 0$ but $\sigma_{\min}(A^T) \neq 0$ in general. This agrees with the identity $\phi(A) = \sigma_{\min}(A)$.</p> <p>However, if one defines the singular values of $A$ to be the diagonal entries of the matrix $\Sigma$ in the singular value decomposition $$A = U\Sigma V^T$$</p> <p>then $A$ and $A^T$ have exactly the same singular values, and $\phi(A) \neq \sigma_{\min}(A)$ in general.</p>