6
$\begingroup$

Let $X(r)$ be the set of matrices $A \in M(n \times m)$, $n \leq m$, such that the norm of $A$ (largest singular value) is smaller or equal than $1$ and the smallest singular value of $A$ is smaller than $r$.

What is the largest exponent $d$ such that the volume of $X(r)$ divided by $r^d$ is uniformly bounded when $r\rightarrow 0$ ?

$\endgroup$

1 Answer 1

1
$\begingroup$

The correct exponent is $d=m-n+1$. Your question is essentially the same thing as: consider a matrix with uniform i.i.d. entries taking values in $[-1,1]$ (this collection of matrices has volume that is a constant factor greater than the ones with norm at most 1); then for what proportion of such matrices is the $n$th row within $r$ of the span of the previous rows?

I am using a claim here: the $n$th singular value of an $n\times m$ matrix agrees up to a bounded factor with $\min_{i}d(r^{(i)},\mathop{lin}\{r^{(j)}\colon j\ne i\})$ that I put in a preprint that I'm just finishing.

So: given the first $n-1$ rows, you're asking what is the probability that the $n$th row lies within $r$ of their span. The span is an $(n-1)$-dimensional space and an $r$-neighbourhood of such a space has volume of the order of $r^{m-(n-1)}$.

$\endgroup$
4
  • $\begingroup$ When you say "bounded factor", you mean "dimension-dependent bounded factor", right? Using for instance the negative second moment identity (see Lemma A.4 of arxiv.org/pdf/0807.4898.pdf) one loses a factor of $\sqrt{n}$ in either direction, and I believe this is tight. $\endgroup$
    – Terry Tao
    Nov 17, 2016 at 1:48
  • $\begingroup$ Right. I'm not making any claims on how the constants depend on $m$ or $n$, but rather how the probability scales as a function of $r$. $\endgroup$ Nov 17, 2016 at 2:54
  • $\begingroup$ PS: @TerryTao: I'm not sure about $\sqrt n$ in both directions. If the quantity is called $\alpha$, I think you can show that $\alpha/\sqrt n\le s_n(A)\le \alpha$. Or maybe I misunderstood the claim? $\endgroup$ Nov 17, 2016 at 6:20
  • $\begingroup$ Ah, yes, you're right, there is only a loss of $\sqrt{n}$ in one direction. $\endgroup$
    – Terry Tao
    Nov 17, 2016 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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