Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
For $m<n$, $\sigma_{\min}$ of $A^T$ is your $\phi$. –  J. M. 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. 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. Sep 3 '10 at 10:11
    
J.M., thanks for your help. –  umar Sep 5 '10 at 5:15
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
    
"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. –  J. M. Sep 3 '10 at 14:59
    
@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. –  Bob Durrant Sep 6 '10 at 11:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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