Table of Contents

T11 Matrix Norms¶

Author: Mark Petersen Email: Mark Petersen

Table of Content

• Introduction
• Operator Norms
• Geometrix Representation
• Bounded Operators
• Submultiplicative Property
• Matrix Norms
• Matrix Norm Relationships
• Example Problem

Introduction¶

This notebook will follow section 4.2 Operator norms in Mathematical Methods and Algorithms for Signal Processing by Todd K. Moon.

Before learning about matrix norms, it is beneficial to look at the definition of a linear operator norm. We will then use this definition to analyze the geometry and boundedness of an operator norm. Then we will look at matrix norms and finish with an example.

Operator Norms¶

There are many ways of defining this norm, and one way to think about it is how much the operator can change the length of the vector it operates on.

Definition Let $X$ and $Y$ be normed vector spaces, and let $A$ be a linear operator $A:X \rightarrow Y$. The $p$ operator norm, or $p$ norm, or $l_p$ norm, of $A$ is

$$||A||_p = \sup_{x \in X, \neq 0} \frac{||Ax||_p}{||x||_p} = \sup_{x \in X, ||x||_p=1} ||Ax||_p$$

where $|| \cdot ||_p$ is the $p$ norm.

Geometric Representation¶

A good way to visually look at how an operator norm changes the length of a vector is to look at how the subordinate matrix norm $||A||_p$ changes the unit circle.

Let $x \in X , ||x||_p = 1$ and $A \in R^{2x2}$ then $||A||_p = \max y$ where $y \in Y$ and $y = Ax$

By visual inspection of the plots above, we can see how $A$ stretches the elements in $X$ when mapping them to elements in $Y$. Notice that the elements along the $x_1$ axis are stretched by a factor of $2$ and the elements along the $x_2$ axis are squeezed by a factor of $0.5$. Since the linear operator $A$ stretched the elements of $x \in X \mid ||x|| = 1$ at most by $2$ then $||A|| = 2$. It is apparent now that the norm doesn't indicate how the linear operator will stretch all of the elements in $X$, rather it indicates the maximum extent it will stretch an element in $X$. i.e.

$$||Ax|| \leq ||A||||x||, \forall x \in X$$

Knowing the most a linear operator will stretch the elements it operates on can help us know if a bounded input $x$ will produce a bounded output $y$.

Bounded Operators¶

The norm of an operator can be used to determine if a linear transformation is bounded, i.e. $A$ will map all finite values in $X$ to finite values in $Y$.

Definition 4.3 If the norm of a transformation is finite, the transformation is said to be bounded.

Using example 4.2.2 from the book.

Let $A:C^1[0,1] \rightarrow C[0,1]$ be the operator

$$Ax = \frac{d}{dt}x$$

The function $x(t) = \sin(w_0t) \in C^1[0,1]$ has uniform norm 1 for any value of $w_0$, but

$$||Ax|| = \max_{t \in [0,1]} w_0|\cos w_0t|$$

may have norm arbitrarily large by choosing $w_0$ to be arbitrarily large. Thus the operator $A$ bounded $\iff w_0$ is not bounded.

By moving the slider in the above figure, you can see as $w_0 \rightarrow \infty, ||Ax|| \rightarrow \infty$ while $x$ stays finite between $0$ and $1$. Thus the norm of the operator is not bounded for every finite value of $x$. The example at the end will show the importance of boundedness.

Submultiplicative Property¶

Suppose you have a system described by $h(t)$ that amplifies audio input $X$. Unfortunately, clipping that is not modeled by the system occurs when the output $\hat{Y}$ is above a certain threshold $y_m$ i.e.

$$\begin{align} \hat{y} & = h(t)*x \\ y & = sat(\hat{y}, y_m) \end{align}$$

whenever clipping occurs, the signal is degraded. So to prevent clipping we want to design $h(t)$ so that clipping never occurs and verify that $||Ax|| \leq y_m \,\, \forall x \in X$. This task could be very difficult if you verified it by brute force. Fortunately, there is a simpler way.

Suppose you knew the largest norm of all the elements in $X$ and you knew $h(t)$, then you could deduce

$$||h(t)*x||_p \leq ||h(t)||||x_m|| \, \forall x \in X$$

where $||x_m|| \geq ||x|| \, \forall x \in X$. This idea uses the submultiplicative property.

Definition Let $X$ and $Y$ be $l_p$ or $L_p$, and let $A$ and $B$ be linear operators. The $p$ norm has the property for all $x \in X$ that

$$||Ax||_p \leq ||A||_p||x||_p$$

Also, the $p$ norm satisfies the submultiplicative property

$$||AB||_p \leq ||A||_p||B||_p$$

From the previous equations we can deduce

$$||ABx||_p \leq ||A||_p||B||_p||x||_p$$

Matrix Norms¶

So far we have generalized our study to any linear operator. The rest of this notebook will specialize on the matrix $p=1$, $p=2$, $p=\infty$ norms and the Frobenius norm.

We will start by creating a basic, python, matrix class and add to it as different matrix norms are introduced.

Norm $p=\infty$¶

Let $A \in \mathbb{C}^{nxm}$, $\mathbf{y} \in \mathbb{C}^n$ and $\mathbf{x} \in \mathbb{C}^m$ the infinity norm is defined as

$$||A||_{\infty} = \max_{||\mathbf{x}||_{\infty}=1} ||A\mathbf{x}||_{\infty} = \max_{i}\sum_{j}|a_{ij}|$$ which is the largest row sum. This is saying that the largest element of $\mathbf{y}$ is composed of the largest row of $A$

By inspecting the above images, you can see that the infinity norm indicates how much $A$ stretches $\mathbf{x}$ along the axes of $\mathbf{y}$

Norm $p=1$¶

The $p=1$ norm is defined as

$$||A||_1 = \max_{||\mathbf{x}||_{1}=1} ||A\mathbf{x}||_{1} = \max_{j}\sum_{i}|a_{ij}|$$ which is the largest column sum.

Norm $p=2$¶

The $p=2$ norm is defined as

$$||A||_2 = \sqrt{\rho(A^HA)}$$

where

$$\rho(A) = \max_i |\lambda_i|$$

i.e. the square-root of the largest eigenvalue of $A^HA$.

Note * The book goes through the derivation of this norm using optimization and principles of eigenvalue that has not yet been covered, so I will skip the derivation of it.

The above figures show how much the unit circle stretches along the eigenvectors of $A$

Frobenius Norm¶

The Frobenius Norm is not a $p$ norm. This norm is often used in matrix analysis since it is relatively easy to compute. It is defined as

$$||A||_F = \sqrt{\mathrm{tr}(A^HA)}$$

i.e. the square root of the sum of all of the elements of $A$ squared.

The Frobenius norm is often used when comparing how similar two matrices $A$ and $B$ are, using $||A-B||_F$.

Matrix Norm Relationships¶

The follow relationships exist between the norms for an $m\times n$ matrix $A$

$$\begin{array}{rcl} ||A||_c & \leq ||A||_F & \leq \sqrt{n}||A||_2 \\ \max_{i,j}|a_{ij}| & \leq ||A||_2 & \leq \sqrt{mn}\max_{i,j}|a_{ij}| \\ \frac{1}{\sqrt{n}}||A||_{\infty} & \leq ||A||_2 & \leq \sqrt{m}||A||_{\infty} \\ \frac{1}{\sqrt{m}}||A||_{1} & \leq ||A||_2 & \leq \sqrt{n}||A||_{1} \end{array}$$

Example Problem¶

Consider a second order mass spring system

$$m\ddot{z} + b\dot{z} + kz = F$$

where $m$ is the mass, $b$ is the damping coefficient, $k$ is the spring constant, $F$ the force being applied and $z$ the displacement of the mass from equilibrium.

The state space representation of the system can be expressed as

$$\dot{x} = Ax + Bu$$

where $A$ represents the internal dynamics of the system, $B$ represents the external dynamics of the system, $x$ represents the position and velocity of the mass, and $u$ represents the input. If we ignore the external dynamics of the system, the state space representation of the system can be expressed as

$$\dot{x} = Ax$$

where

$$A= \begin{bmatrix} 0 & 1 \\ -k/m & -b/m \end{bmatrix}$$

The solution to the second order system is

$$x(t) = \exp^{-A t}x_0$$

by inspection, we can analyze $A$ to determine the rate of decay or how fast the perturbed system returns to equilibrium by analyzing the norm of $A$. The larger $||A||$ is, the faster the system moves to equilibrium. In essence, $||A||$ measures how fast a system can change. You can interact with the graph below to see the effect the matrix norm of $||A||$ on the system's response.