1
$\begingroup$

Suppose that $A$ is an $n$ by $n$ Gaussian matrix (each component i.i.d. normal distributed with mean 0 and variance 1). Let $b$ be a $n$-Gaussian vector. Then it could be easily proven that the median of $||A^{-1}b||_2$ is roughly $O(\sqrt{n})$, i.e. $||A^{-1}b||_2\le O(\sqrt{n})$ with high probability.

Similarly, if $B$ is an $n$ by $n$ Gaussian matrix, then it could be proven that $||A^{-1}B||_2\le O(n)$ with high probability.

However, I did some experiments and found that $$\max_{j\in[n]}||(A^{-1}B)_{\cdot j}||_2 \ ,$$ the maximum column $l_2$ norm of $A^{-1}B$, looks like to be bounded by $O(\sqrt{n})$ instead of $O(n)$. This is so interesting because it is of the same order of the norm for only one column.

Does anyone know how to prove a high-probability upper bound result of the maximum column norm?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I think it is more likely to be $\asymp\sqrt n\,\ln n$. For $n$ not too large, numerical experiments may not detect the log factor. $\endgroup$
    – Iosif Pinelis
    Commented Apr 12 at 16:55
  • $\begingroup$ I see. That is still very interesting for me. Do you know any references or evidence for this result? Or are there any suggestions on how should I prove it? Thanks so much. $\endgroup$
    – ZZZZZZ
    Commented Apr 12 at 17:54
  • $\begingroup$ Unfortunately, I don't have such references or evidence. $\endgroup$
    – Iosif Pinelis
    Commented Apr 12 at 17:57
  • $\begingroup$ Still, thank you so much for providing this intuition. $\endgroup$
    – ZZZZZZ
    Commented Apr 12 at 18:02
  • $\begingroup$ What is the median for you ? The mean or (50% below , 50% above). $\endgroup$
    – loup blanc
    Commented May 2 at 13:58

1 Answer 1

Reset to default
1
$\begingroup$

We write about the median -not the mean which is significantly greater- of $||A^{-1}b||_2$.

I am surprised by the conjecture made by @Iosif Pinelis according to which the considered median $m_n$ would be in $O(\sqrt{n}log(n))$.

Note that $m_1=1$. I did random tests according to which $m_n$ seems to behave at infinity like $k\sqrt{n}$.

More precisely, $m_{60},m_{100},m_{140}$ are $\approx k\sqrt{n}$, where $k\in (1.46,1.47)$.

I have no argument that would justify this result. Note, however, that it is often more difficult to evaluate a median than an average.

Improve this answer
$\endgroup$

You must log in to answer this question.

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