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

  • 1
    $\begingroup$ For $m<n$, $\sigma_{\min}$ of $A^T$ is your $\phi$. $\endgroup$ – J. M. is not a mathematician Sep 3 '10 at 6:19
  • $\begingroup$ "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. $\endgroup$ – J. M. is not a mathematician Sep 3 '10 at 6:20
  • $\begingroup$ 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? $\endgroup$ – umar Sep 3 '10 at 8:02
  • $\begingroup$ umar: An $m\times n$ matrix has $\min(m,n)$ singular values. $\endgroup$ – 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.


These very useful notes will probably be of interest to you: http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf starting at page 7.

  • $\begingroup$ 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. $\endgroup$ – umar Sep 3 '10 at 14:18
  • $\begingroup$ "smallest singular value of a wide matrix is 0" - That sounds dodgy. As mentioned already, the number of singular values is the smallest of the two dimensions. $\endgroup$ – J. M. is not a mathematician Sep 3 '10 at 14:59
  • $\begingroup$ @J.M. Not at all dodgy I think, but a matter of interpretation/definition. The number of non-zero SVs will be the smallest of the two dimensions, so if we define away the zeroes then your assertion is fine. I don't know if one version of the definition is more accepted than the other, but certainly umar's matrix A has a non-trivial kernel! PS One of the nice things about random projection matrices is that one can show (typically almost surely, although it depends on how the matrix entries are constructed) that points of interest do not lie in the kernel of A, which sidesteps many issues. $\endgroup$ – Bob Durrant Sep 6 '10 at 11:19

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.