2
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – Rahul Jul 15 '16 at 1:36
  • $\begingroup$ 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? $\endgroup$ – mathplebeian Jul 16 '16 at 22:35
5
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ah, I see! Thank you for enlightening me on this matter. $\endgroup$ – mathplebeian Jul 15 '16 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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