# 2-norm vs operator norm

I have read that we define the "2-norm" of a matrix as

$$\max_i \,{|\sigma_i|},$$

which I have also heard called the "operator norm" (here $\sigma_i$ are the singular values).

Also we have the norms

$$\|A\| = \left( \sum_{i,j}|a_{ij}|^q \right)^{1/q}$$

for every $q\geq 1$. Do we refer to these as $\|A\|_q$? (For $q=2$, I have heard this referred to as the "Frobenius norm".) If we do refer to them as $\|A\|_q$, then how can we reconcile the two meanings of the term "two-norm"?

Subquestion: How can we bound the values of $\|A\|$ for $q=1$ and $q=2$ in terms of each other?

-
What is $\sigma_i$ in the first definition? – Prahlad Vaidyanathan Sep 2 '13 at 15:37
Edited, sorry.--- – Eric Auld Sep 2 '13 at 15:38
Do you mean the singular values of $A^{\ast}A$? Because otherwise what you say is not true. – Prahlad Vaidyanathan Sep 2 '13 at 15:50
@PrahladVaidyanathan I understand that the "singular values of $A$" refers to the moduli of the eigenvalues of $A^* A$. That is consistent with the definition here: en.wikipedia.org/wiki/Singular_value – Eric Auld Sep 2 '13 at 15:52
Or rather, the square roots of those moduli. – Eric Auld Sep 2 '13 at 16:10

I think I understand your question - typically $\|A\|_2$ has two definitions $$\|A\|_2 = \sqrt{\text{largest eigen value of } A^{\ast}A}$$ and $$\|A\|^{\prime}_2 = \sup_{\|x\|_2 = 1}\|Ax\|_2$$ Note that $B = A^{\ast}A$ is a symmetric, positive matrix ($\langle Bx,x \rangle \geq 0$), and hence it can be diagonalized, and its eigen values are non-negative. Write them as $$\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n \geq 0$$ and consider an orthonormal basis $\{u_1, u_2, \ldots, u_n\}$ such that $$Bu_i = \lambda_i u_i$$ For any $x \in \mathbb{R}^n$, write $x = \sum \alpha_i u_i$, then $$\|x\|_2 = 1 \Leftrightarrow \sum_{i=1}^n \alpha_i^2 = 1$$ So consider $$\|Ax\|^2_2 = \langle Ax,Ax\rangle = \langle A^{\ast}Ax,x\rangle = \sum_{i=1}^n \lambda_i \alpha_i^2$$ Hence, it follows that $$\|Ax\|^2_2 \leq \lambda_1$$ and hence $\|A\|^{\prime}_2 \leq \sqrt{\lambda_1} = \|A\|_2$

The other inequality is obvious - can you see that?

-

The operator norm of a matrix depends on the norm that you are putting on the vector space on which it acts. So for example if the matrices we are consider are in $M_n(\mathbb{R})$ then they are acting on $\mathbb{R}^n$. Given a norm $\|\cdot\|_\alpha$ on $\mathbb{R}^n$ we can create an associated norm (operator norm associated to $\alpha$) by defining

$\|A\|_{(\alpha)}=\sup_{v\neq0}\frac{\|Av\|_\alpha}{\|v\|_\alpha}$.

In the case that we are using the usual euclidean 2-norm for $\mathbb{R}^n$ then the associated $\|\cdot\|_{(2)}$ is what you describe above.

However, we also know that $M_n(\mathbb{R})$ is a vector space isomorphic to $\mathbb{R}^{n^2}$ and so we can put a norm on it this way. These are the $\|A\|_q$ norms that you mention.

In particular $\|A\|_2=\left(\sum|a_{ij}|^2\right)^{\frac{1}{2}}\neq \|A\|_{(2)}$ in general.

Take for example $A=\left(\begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array}\right)$

Then $\|A\|_{(2)}=2$ and $\|A\|_2=\sqrt{5}$

Finally just like any finite dimensional space we have $\|A\|_1\geq \|A\|_2$. Further for finite dimensional spaces all norms give the same topology. This implies that for any two norms and any $A$ in the space there are constants $k_1, k_2>0$ such that $\|A\|_\alpha\geq k_1\|A\|_\beta\geq k_2\|A\|_\alpha$.

Thus there is some constant such that $\|A\|_2\geq k\|A\|_1$ but I don't know what it is off the top of my head. (and it should depend on $n$...maybe $\sqrt{n}$?)

-

The operator norm is a matrix/operator norm associated with a vector norm. It is defined as

$||A||_{\text{OP}} = \text{sup}_{x \neq 0} \frac{|A x|_n}{|x|}$

and different for each vector norm. In case of the Euclidian norm $|x|_2$ the operator norm is equivalent to the 2-matrix norm (the maximum singular value, as you already stated). So every vector norm has an associated operator norm, for which sometimes simplified expressions as exist.

The Frobenius norm (i.e. the sum of singular values) is a matrix norm (it fulfills the norm axioms), but not an operator norm, since no vector norm exists so that the above definition for the operator norm matches the Frobenius norm.

As far as I know the "q-matrix norms" as you define them (I have never seen these before, and I am also not sure if these fulfill the norm axioms) do not match the q-vector norms as corresponding operator norm in the general case (this is more complicated, I think).

-
I think you are incorrect in your statement about the operator norm associated to the Euclidean norm. See my answer below – Owen Sizemore Sep 2 '13 at 15:57
I dont see any difference between your statement and mine, in regard of the operator norm associated with the Euclidian norm. Can you be more specific? – Andreas H. Sep 2 '13 at 16:09
The operator norm associated to the Euclidean norm is not the same as the Euclidean norm on the matrix algebra (I assume this is what you mean by the 2-matrix norm). – Owen Sizemore Sep 2 '13 at 17:33
yes and no: the Euclidian norm for matrices is called Frobenius norm (en.wikipedia.org/wiki/Matrix_norm#Frobenius_norm) and denoted by $||A||_F$ and this is distinct from the "true" 2-norm for matrices, which is by definition the operator norm to the 2-norm for vectors. But looking at the wikipedia page, there is some inconsistency in the nomenclature: $||A||_p$ can refer both to the entrywise and the induced norms, whereas I personally would assume that it always refers to the latter because that is more useful. And the Frobenius norm (which is useful for itself) has a special name. – Andreas H. Sep 2 '13 at 19:00