# Equivalent Definitions of the Spectral Norm

There are many equivalent definitions of the spectral norm $\|A\|_2$ for when $A$ is a symmetric matrix, the most common ones being

$$\sup_{\|x\|_{2} = 1}{\|Ax\|_{2}} = \sup_{\|x\|_{2}=1}|{\langle Ax,x \rangle|} = \text{largest eigenvalue of A in absolute value}$$

Recently, while going through a paper on compressed sensing (http://statweb.stanford.edu/~candes/papers/PartialMeasurements.pdf), I was met with the following definition of the spectral norm(search "spectral" in the paper):

$$\|Y\|_2 = \displaystyle\sup_{\|f_1\|_{2} = \|f_1\|_{2} = 1 } \langle f_1, Yf_2 \rangle$$

where $f_1, f_2$ are unit norm vectors. After going through some naive calculations, I could not find out why this norm is equivalent to the ones I defined above, nor have I found another source that defines it this way. I was wondering if someone can clear this up for me as to why the definitions are equivalent.

Thanks all beforehand!

• Useful lemma: $\sup_{\|y\|=1} \langle y,x\rangle = \|x\|$. Therefore $\sup_{\|x\|=\|y\|=1} \langle y,Ax\rangle = \sup_{\|x\|=1}(\sup_{\|y\|=1} \langle y,Ax\rangle) = \cdots$ – Rahul Jul 15 '16 at 1:36
• I know I did not state what kinds of vectors f1 and f2 are, but I assume the definitions are equivalent only when f1, f2, and A are all real? Otherwise the inner product could spit out a complex number? – mathplebeian Jul 16 '16 at 22:35

Clearly $\sup_{\|x\|_{2}=1}|{\langle Ax,x \rangle|} \leq \sup_{\|f_1\|_{2} = \|f_1\|_{2} = 1 } \langle f_1, Af_2 \rangle$. The reverse inequality can be proven in several ways. For instance, by the spectral theorem, we may assume that $A$ is diagonal. If every eigenvalue of $A$ has absolute value $\leq C$ and we have two vectors $f_1=(f_1^1,\dots,f_1^n)$ and $f_2=(f_2^1,\dots,f_2^n)$, we have $$\langle f_1,Af_2\rangle=\sum_i f_1^i A_{ii}f_2^i\leq C\sum_i |f_1^if_2^i|\leq C\|f_1\|_2\|f_2\|_2.$$ We can conclude that $\sup_{\|f_1\|_{2} = \|f_1\|_{2} = 1 } \langle f_1, Af_2 \rangle\leq C$.