# 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$.

• For $m<n$, $\sigma_{\min}$ of $A^T$ is your $\phi$. – J. M. is not a mathematician Sep 3 '10 at 6:19
• "although I am not certain why this is true" - books on numerical linear algebra devote a paragraph or two to this, since this is related to the discussion of the conditioning of least squares problems. – J. M. is not a mathematician Sep 3 '10 at 6:20
• J.M. -- Thanks. I don't understand your claim that $\phi(A) = \sigma_{min}(A^T)$ when $m < n$. Isn't it the case that $\sigma_{min}(A^T) = \sigma_{min}(A)$? So doesn't my $m = 1$ and $n > 1$ counterexample still apply? – umar Sep 3 '10 at 8:02
• umar: An $m\times n$ matrix has $\min(m,n)$ singular values. – J. M. is not a mathematician Sep 3 '10 at 10:11

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 < 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)$.
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$$
then $A$ and $A^T$ have exactly the same singular values, and $\phi(A) \neq \sigma_{\min}(A)$ in general.
• Bob, thanks for your reply. I must be missing something very elementary. The notes you point me to say on page 7 that $\sigma_{\min}(A) = 0$ whenever $m < n$. But later on page 7 it says that $\sigma_{\min}(A) = \frac{1}{\lVert A^\dagger \rVert}$, where $A^\dagger$ is the pseudoinverse of $A$. But this latter quantity is non-zero. – umar Sep 3 '10 at 14:18