A function $\|\cdot\|: \mathbb{C}^m \rightarrow \mathbb{R}$ is a norm iff:
Often denoted as $\|x\|$.
Other norms are: \begin{eqnarray} \|x\|_1 & = & \left|x_1\right| + \left|x_2\right| + \dots + \left|x_N\right| \end{eqnarray}
\begin{eqnarray} \|x\|_\infty & = & \max\{\left|x_1\right|,\left|x_2\right|,\dots,\left|x_N\right|\} \end{eqnarray}and more general $p$ norms \begin{eqnarray} \|x\|_p & = & \left( \left|x_1\right|^p + \left|x_2\right|^p + \dots + \left|x_2\right|^p\right)^{\frac{1}{p}} \end{eqnarray}
In [2]:
%run plot_normballs.py
Matrix Norm:
This is the maximum $p$-norm of the vector $Ax$ where $x$ is an element of the unit $q$-norm-ball.
Below, we show the image $Y$ of a set of points on the unit $q$-norm ball, i.e. $Y = \{y : y = Ax; \|x\|_q = 1 \}$. The dotted lines are the points that have $\|y\|_p = r$.
Given the image, what can you say about $\|A\|_{(p,q)}$ ?
In [1]:
%matplotlib inline
import numpy as np
np.set_printoptions(precision=3, suppress=True)
%run matrix_norm_sliders.py
$\|A\|_F = \sqrt{Tr(A^\top A)}$
We show that the function $\|A\|_F$ is a norm:
Nonegativity and Scaling are obvious. The triangle inequality is:
\begin{eqnarray} \|A + B \|_F^2 & = & Tr((A + B)^\top (A + B) ) \\ & = & Tr(A^\top A + B^\top B + A^\top B + B^\top A) \\ & = & Tr(A^\top A) + Tr(B^\top B) + 2 Tr(B^\top A) \\ & = & \|A\|_F^2 + \|B\|_F^2 + 2 Tr(B^\top A) \\ & \leq & \|A\|_F^2 + \|B\|_F^2 + 2 |Tr(B^\top A)| \\ & \leq & \|A\|_F^2 + \|B\|_F^2 + 2 \|A\|_F \|B\|_F \\ & = & (\|A\|_F + \| B \|_F)^2 \end{eqnarray}Cauchy-Schwarz for the Frobenius norm \begin{eqnarray} |Tr(B^\top A)| \leq \|A\|_F \|B\|_F \end{eqnarray} holds as \begin{eqnarray} Tr(B^\top A) & = & vec(B)^\top vec(A) \\ \|A\|_F & = & \|vec(A)\|_2 \end{eqnarray}
Let $C = AB$. Hence, $c_{i,j} = a_i^\top b_j$ where $a_i^\top$ is the $i$'th row of $A$ and $b_j$ is the $j$'th column of $B$
\begin{eqnarray} \| A B \|_F^2 & = & \sum_{i} \sum_j |c_{i,j} |^2 \\ & = & \sum_{i} \sum_j |a^\top_{i} b_j |^2 \\ & \leq & \sum_{i} \sum_j \|a_i\|^2 \|b_j\|^2 \\ & = & \left(\sum_{i} \|a_i\|^2 \right) \left(\sum_j \|b_j\|^2 \right)\\ & = & \| A \|_F^2 \| B \|_F^2 \\ \end{eqnarray}Hence $$ \| A B \|_F \leq \| A \|_F \| B \|_F $$
Calculate the points in polar coordinates.
In $2$D, take rays of the form $$x = \left( \begin{array}{c} x_1 \\ x_2 \end{array} \right) = \left( \begin{array}{c} \alpha \cos(\theta) \\ \alpha \sin(\theta) \end{array} \right) $$ where $\alpha>0$ and $0\leq \theta \leq 2\pi$.
The $p$-norm of a vector $x$ with $\|x\|_p = 1 $ satisfies
$\left|x_1\right|^p + \left|x_2\right|^p = \alpha^p (\left|\cos(\theta)\right|^p + \left|\sin(\theta)\right|^p) = 1 $
Solve for $\alpha(\theta)$: $$\alpha = \left(\frac{1}{\left|\cos(\theta)\right|^p + \left|\sin(\theta)\right|^p}\right)^{1/p} $$
Prove that $\|x\|_W = \|Wx\|$ is a norm for any nonsingular matrix.
$\|x\|_W $ is nonnegative as $\|\cdot\|$ is.
Assume $x\neq 0$ and $$ Wx = 0 $$. But as $W$ is nonsingular we have $x = W^{-1} 0 = 0$, that leads to a contradiction.
Let $B$ be a submatrix of $A$.
Dual norm $\|x\|' = \sup_{\|y\|=1} \left| y^* x \right| $
In [11]:
%matplotlib inline
from mpl_toolkits.mplot3d import axes3d
import matplotlib.pyplot as plt
from notes_utilities import pnorm_ball_points
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
# Grab some test data.
x = np.arange(-2,2,0.1)
X, Y = np.meshgrid(x, x)
p2 = 2
p = p2
Z2 = (np.abs(X)**p + np.abs(Y)**p)**(1./p)
p1 = 5
p = p1
Z = (np.abs(X)**p + np.abs(Y)**p)**(1./p)
r = 2
dx, dy = pnorm_ball_points(p=p1)
ax.plot(r*dx,r*dy,r*np.ones_like(dx), color='b')
ax.plot(r*dx,r*dy,np.sqrt(2.)*r*np.ones_like(dx), color='g')
dx, dy = pnorm_ball_points(p=p2)
ax.plot(r*dx,r*dy,r*np.ones_like(dx), color='r')
# Plot a basic wireframe.
ax.plot_wireframe(X, Y, Z, rstride=4, cstride=4)
ax.plot_wireframe(X, Y, Z2, rstride=4, cstride=4, color='r' )
ax.plot_wireframe(X, Y, np.sqrt(2.)*Z, rstride=4, cstride=4, color='g' )
plt.show()