<jupyter_start><jupyter_text>NormsA function $\|\cdot\|: \mathbb{C}^m \rightarrow \mathbb{R}$ is a norm iff:* (Nonnegativity) $\|x\| \geq 0$, $\|x\| = 0 \Leftrightarrow x = 0$* (Triangle Inequality) $\|x+y\| \leq \|x\| + \| y \|$* (Scaling) $\|\alpha x\| = |\alpha|\|x\|$  for a scalar $\alpha$,   Vector Norms The Euclidian $\ell_2$ norm \begin{eqnarray}\|x\|_2 & = & \left(x_1^2 + x_2^2 + \dots + x_N^2\right)^{\frac{1}{2}}\end{eqnarray}Often denoted as $\|x\|$. The $\ell_1$ and $\max$-norms 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} $p$-normand 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}  Norm BallsGiven a $p \geq 1$, a $p$-norm ball is the set of points $$B_p = \{ x : \| x \|_p \leq 1 \}$$<jupyter_code>%run plot_normballs.py<jupyter_output><empty_output><jupyter_text>Weighted normsFor an arbitrary nonsingular matrix $W$,$$\|x\|_W = \|Wx\| $$  The Matrix normMatrix Norm:* (Nonnegativity) $\|A\| \geq 0$, $\|A\| = 0 \Leftrightarrow A = 0$* (Triangle Inequality) $\|A+B\| \leq \|A\| + \| B \|$* (Scaling) $\|\alpha A\| = |\alpha|\|A\|$  for a scalar $\alpha$,  \begin{eqnarray}\|A\|_{(p,q)} = \sup_{\|x\|\neq 0} \frac{\|A x\|_{(p)}}{\|x\|_{(q)}} = \sup_{\|x\|_{(q)} = 1} {\|A x\|_{(p)}}\end{eqnarray}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)}$ ?<jupyter_code>%matplotlib inline
import numpy as np
np.set_printoptions(precision=3, suppress=True)


%run matrix_norm_sliders.py<jupyter_output>/Users/cemgil/anaconda/envs/py27/lib/python2.7/site-packages/matplotlib/font_manager.py:273: UserWarning: Matplotlib is building the font cache using fc-list. This may take a moment.
  warnings.warn('Matplotlib is building the font cache using fc-list. This may take a moment.')<jupyter_text>Frobenius Norm $\|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$$  Drawing norm-balls in 2-DCalculate 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} $$  3.1 Prove that $\|x\|_W = \|Wx\|$ is a norm for any nonsingular matrix.* Nonnegativity $\|x\|_W \geq 0$, $\|x\|_W = 0$ iff $x=0$.$\|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.* Scaling $$ \|\alpha x\|_W = \|\alpha Wx\| = \left|\alpha\right| \|Wx\| = \left|\alpha\right|\| x\|_W$$* Triangle Inequality$$ \|\ x+ y \|_W = \|Wx+Wy\| \leq \|Wx\| + \|Wy\| = \|x\|_W + \|y\|_W $$ 3.3$$\|x\|_\infty \leq \|x\|_2$$$$\|x\|_2 \leq \sqrt{2} \|x\|_\infty $$ 3.4Let $B$ be a submatrix of $A$. * How can we choose $E_r$ and $E_c$ to write $B = E_r A E_c$* Show that $\|B\| \leq \|A\|$ 3.6Dual norm $\|x\|' = \sup_{\|y\|=1} \left| y^* x \right| $<jupyter_code>%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()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.25660773674076665, 'fraction_numerical': 0.021704883598809732, 'mean_word_length': 3.506309148264984, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '179996', 'license': 'MIT', 'n_tokens_mistral': 2539, 'n_tokens_neox': 2408, 'n_words': 604, 'path': 'Norms.ipynb', 'repo_name': 'bkoyuncu/notes', 'size': '5713'}