Equivalent Definitions of the Spectral Norm

Question

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!

Answer 1

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

Answer 2

On one hand, \begin{align} \sup_{\|f_1\|=\|f_2\|=1} | \langle f_1, Yf_2\rangle| &\ge \sup_{\|f_2\|=1,Yf_2 \ne 0} |\langle \frac{1}{\|Yf_2\|}Yf_2,Yf_2\rangle| \\ & =\sup_{\|f_2\|=1,Yf_2\ne 0} \|Yf_2\| \\ & = \sup_{\|f_2\|=1}\|Yf_2\| =\|Y\| \end{align} On the other hand, \begin{align} \sup_{\|f_1\|=\|f_2\|=1} |\langle f_1,Yf_2\rangle| &\le \sup_{\|f_1\|=\|f_2\|=1} \|f_1\|\|Yf_2\| \\ &= \sup_{\|f_1\|=\|f_2\|=1}\|Yf_2\| \\ &=\sup_{\|f_2\|=1}\|Yf_2\| = \|Y\|. \end{align}