1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ For $m<n$, $\sigma_{\min}$ of $A^T$ is your $\phi$. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 3, 2010 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. isn't a mathematician
    Commented Sep 3, 2010 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
    Commented Sep 3, 2010 at 8:02
  • $\begingroup$ umar: An $m\times n$ matrix has $\min(m,n)$ singular values. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 3, 2010 at 10:11

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 3, 2010 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. isn't a mathematician
    Commented Sep 3, 2010 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
    Commented Sep 6, 2010 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .