### Operator Norms Given any vector norm $\| \cdot \|$, we can define a corresponding **operator norm** of a matrix $A$ to be $\| A \| := \max_{x} \frac{\| Ax \| }{\| x \| }.$ For many norms, the operator norm can be expressed in terms of the matrix itself: For $l_{2}$ norm, $\| A \|_{2}=\sigma_{1}(A)$, the largest [[Singular Value Decomposition|singular value]]: ![[Singular Value Decomposition#^0600ec]] For the $l_{1}$ norm, $\| A \|_{1}=\max_{j}\| a_{j} \|_{1}$, where $a_{j}$ is the $j$th column of $A$. This is because $\| Ax \| _{1}=\left\| \sum_{j}x_{j}a_{j} \right\| \le \sum_{j} \| x_{j} a_{j} \|\le \| x \|_{1}\cdot \max_{j}\| a_{j} \|,$and we can achieve this upper bound by concentrating all weights onto the largest column of $A$ (say the $j^{\ast}$th). That is, the maximiser is $x=e_{j^{\ast}}$, where $j^{\ast}=\underset{j}{\arg\max}~\| a_{j} \|_{1}$. For the infinity norm, $\| A \|_{\infty}= \max_{i}\| a_{i, :} \|_{1},$ where $a_{i,:}$ is the $i$th row of $A$. This is because $\| Ax \| _{\infty}= \max_{i}| a_{i, :}^{T}x |\le \max_{i} \| a_{i,:} \|_{1}\cdot \| x \| _{\infty}, $ using the identity $| a^{T} x |=| \sum_{j}a_{j}x_{j} | \le \sum_{j}| a_{j} |\cdot | x_{j} |\le \sum_{j}| a_{j} |\cdot \| x \|_{\infty}=\| a \|_{1}\| x \|_{\infty}$. We achieve this upper bound with $x_{\infty}\propto\mathrm{sign}(a_{i^{\ast}})$, i.e. with the $j$th entry equalling the sign of $a_{i^{\ast}j}$, and $i^{\ast}:= \underset{i}{\arg\max}~\| a_{i,:} \|_{1}$. ### Operator Norm Equivalencies Here let $x_{p}:= \underset{x: \| x \|_{p}=1}{\arg\max}~\| Ax \|_{p}$ be the maximisers of the matrix p-norms, for $p=1,2,\infty$. $\| A \|_{2} \in \| A \| _{\infty} \cdot \left[ \frac{1}{\sqrt{ n }}, \sqrt{ m } \right], $ with the lower bound achieved by $A=e_{1} \mathbf{1}^{T}$ (i.e. the matrix with the first row filled with $1$, and the rest $0$), which has $\| A \|_{\infty}=n$ and $\| A \|_{2}=\| \mathbf{1} \|_{2}= \sqrt{ n }$. The lower bound is achieved by its transpose, with $\| A \|_{2}=\sqrt{ n }$ and $\| A \|_{\infty}=1$. > [!proof] > The lower bound follows from $\| A \|_{\infty}=\| Ax_{\infty} \|_{\infty} \le \| Ax_{\infty} \|_{2}\le \| A \|_{2}\| x_{\infty} \|_{2}=\sqrt{ n }\| A \|_{2}.$ > > The upper bound is from > $\| A \|_{\infty} \ge \frac{\| Ax_{2} \| _{\infty}}{\| x_{2} \| _{\infty}}\ge \| Ax_{2} \|_{\infty}\ge \| Ax_{2} \|_{2} / \sqrt{ m } =\| A \|_{2} / \sqrt{ m } .$ > The second and third inequalities are based on the vector norm identities $\| x_{2} \|_{2} / \sqrt{ m }\le \| x_{2} \|_{\infty}\le \| x_{2} \|_{2}$, and $\| x_{2} \|_{2}=1$. $\| A \|_{2}\in \| A \| _{1} \left[ \frac{1}{\sqrt{ m }}, \sqrt{ n } \right] $ Again, the lower and upper bounds are achieved by $A^{T}=\mathbf{1}e_{1}^{T}$ (with $\| A \|_{2}=\sqrt{ n }$ and $\| A \|_{1}=1$) and $A=e_{1}\mathbf{1}^{T}$ (with $\| A \|_{1}= \frac{1}{n}$) respectively. > [!proof] > The lower bound is from $\| A \|_{2}\ge\| Ax_{1} \| _{2}\cdot\| x_{1} \|_{2} \overset{!}{\ge} \frac{1}{\sqrt{ m }}\| Ax_{1} \| _{1} = \frac{1}{\sqrt{ m }}\| A \| _{1}.$ > Here the inequality marked with $!$ is from the vector norm inequality $\| v \|_{2}\ge \| v \|_{1} / \sqrt{ m},$ for vectors $v\in \mathbb{R}^{m}$. > > The upper bound is from $A_{2}=\| Ax_{2} \|_{2}\le \| Ax_{2} \| _{1}\le \| A \| _{1}\| x_{2} \| _{1}\overset{!}{\le} \| A \| _{1} \cdot \sqrt{ n } \| x_{2} \| _{2}=\sqrt{ n }\| A \| _{1}.$ > Again the $!$ follows from the same inequality, applied to $x_{2}\in \mathbb{R}^{n}$, the first right singular vector of $A$. $\| A \| _{2}\in \| A \|_{F} \left[ \frac{1}{ \sqrt{ \min (m,n) }} , 1\right] $ The bounds are achieved by $A=I$ and $A=(\delta_{1,1}(i,j))$ respectively. > [!proof] > Both norms are invariant under orthogonal maps, so left and right apply $U^{T}, V$ respectively, where $U,V$ are the orthogonal matrices in the SVD of $A$. So $\| A \|_{2}=\| \Sigma \|_{2}=\sigma_{1}(A)$, and $\| A \|_{F}=\| \Sigma \|_{F}=\sqrt{ \sum_{i}\sigma_{i}(A)^{2} }$. > > The upper bound is then obvious, and the lower bound is from $\sum_{i=1}^{\min(m,n)}\sigma_{i}(A)^{2}\le \min(m,n)\max_{i}\sigma_{i}(A)^{2}=\min(m,n)\| A \| _{2}^{2}.$