2
$\begingroup$

We are given a matrix $A=(A_1, \dots, A_n)$ where $A_i \in \mathbb{R}^m$. Moreover, $||A_i||_2=1$.

This yields for example for the frobeniusnorm $||A||_F=\sqrt{\sum_{i=1}^n ||A_i||_2^2} = \sqrt{n} $ or for the infinity norm $||A||_\infty = \max_{i=1, \dots, m} \sum_{j=1}^n |(A_{j})_i|\leq \max_{i=1, \dots, m} \sum_{j=1}^n 1 \leq n.$

Does this also give us an upper bound on the spectral norm of $A$? I know that the spectral norm is the largest singular value of $A$ and an intuitive interpretation is that the spectral norm gives how much the matrix can 'scale' a vector. So I would guess there is a connection between the columns of $A$ being normalized to $1$ and the size the spectral norm can obtain, but I don't see it.

It is not diffictult to prove that the spectral norm yields a lower bound of $1$ in this case since: $||A||_2=\max_{||v||=1} ||Av||_2 \geq ||Ae_i||_2 = ||A_i||_2 = 1$.

$\endgroup$
2
  • $\begingroup$ What if the rank of $A$ is 1? $\endgroup$
    – cangrejo
    Commented Aug 13, 2021 at 7:45
  • $\begingroup$ What would happen in this case? $\endgroup$
    – samabu
    Commented Aug 13, 2021 at 7:53

2 Answers 2

4
$\begingroup$

Since each column of $A$ is a unit vector, for any unit $v\in\mathbb R^m$, $v^TA$ is entrywise between $-1$ and $1$. It follows that $\|v^TA\|_2\le\sqrt{n}$. Hence $\|A\|_2\le\sqrt{n}$. Equality occurs when each column of $A$ is $\pm$ column 1.

$\endgroup$
3
  • $\begingroup$ Hello, thank you for your answer. Why do you compute $v^TA$ and not $Av$ for the norm? $\endgroup$
    – samabu
    Commented Aug 13, 2021 at 8:23
  • $\begingroup$ This is incorrect. Consider $m=1$, $v=1$. $\endgroup$
    – cangrejo
    Commented Aug 13, 2021 at 8:27
  • 1
    $\begingroup$ @cangrejo It's a typo. Fixed by now. $\endgroup$
    – user1551
    Commented Aug 13, 2021 at 8:32
1
$\begingroup$

$\|A\|_F = \sqrt{\sum_{i=1}^n \sigma_i^2}$, where $\sigma_i$ is the $i$-th singular value of $A$.

The number of non-zero singular values equals the rank of $A$.

Thus, the spectral norm can be as large as $\sqrt n$ if the rank of $A$ is one.

$\endgroup$
3
  • 1
    $\begingroup$ What does this have to do with the rank of $A$ being one? Can't we obtain this bound for larger ranks as well? $\endgroup$
    – samabu
    Commented Aug 13, 2021 at 9:13
  • 1
    $\begingroup$ @samabu The bound follows immediately from the inequalities relating Frobenius and spectral norms (which in turn follow from the sum), so the question is rather whether we can improve it. The fact that it is tight (i.e. we can't) becomes clear in the rank-one case. If the rank of $A$ is one, then there is only one non-zero entry in the above sum. This rules out any smaller bound for the spectral norm in your case. $\endgroup$
    – cangrejo
    Commented Aug 13, 2021 at 12:03
  • $\begingroup$ Ah ok, thank you. Now I understand the answer $\endgroup$
    – samabu
    Commented Aug 13, 2021 at 13:06

You must log in to answer this question.

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