Maximum stretch and singular values

Section 6.3 Maximum stretch and singular values

One way to ask what a matrix map does is to ask which unit input is stretched the most:

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|^2. \end{equation*}

The square is included because

\begin{align*} \|A\mathbf{x}\|^2\\ \amp = (A\mathbf{x})\cdot(A\mathbf{x})\\ \amp = \mathbf{x}^T A^T A\mathbf{x}. \end{align*}

Thus a question about a matrix map becomes a constrained optimization problem for the scalar-valued function

\begin{equation*} \mathbf{x}\mapsto \mathbf{x}^T A^T A\mathbf{x} \end{equation*}

on the unit sphere.

🔗

Fact 6.3.1.

Let \(B\) be a symmetric matrix, and define

\begin{equation*} q(\mathbf{x})=\mathbf{x}^T B\mathbf{x}. \end{equation*}

The extrema of \(q(\mathbf{x})\) subject to \(\|\mathbf{x}\|=1\) occur at eigenvectors of \(B\text{.}\) The extreme values are eigenvalues of \(B\text{.}\)

🔗

Why is this true?.

Use the constraint

\begin{equation*} g(\mathbf{x})=\mathbf{x}\cdot \mathbf{x}=1. \end{equation*}

For symmetric \(B\text{,}\)

\begin{equation*} \nabla q(\mathbf{x})=2B\mathbf{x}, \qquad \nabla g(\mathbf{x})=2\mathbf{x}. \end{equation*}

The Lagrange multiplier condition gives

\begin{equation*} 2B\mathbf{x}=\lambda 2\mathbf{x}, \end{equation*}

\begin{equation*} B\mathbf{x}=\lambda \mathbf{x}. \end{equation*}

Thus constrained critical points occur at eigenvectors of \(B\text{.}\) If \(\mathbf{x}\) is a unit eigenvector with \(B\mathbf{x}=\lambda\mathbf{x}\text{,}\) then

\begin{align*} q(\mathbf{x}) \amp= \mathbf{x}^T B\mathbf{x}\\ \amp = \mathbf{x}^T(\lambda\mathbf{x})\\ \amp = \lambda\|\mathbf{x}\|^2\\ \amp = \lambda. \end{align*}

Since the unit sphere is closed and bounded, the extreme value theorem guarantees that the extrema occur among these candidates.

🔗

Apply the fact to \(B=A^TA\text{.}\) The eigenvalues of \(A^TA\) are nonnegative, so we can take their square roots. The singular values of \(A\) are

\begin{equation*} \sigma_i=\sqrt{\lambda_i}, \end{equation*}

where \(\lambda_i\) are the eigenvalues of \(A^TA\text{,}\) listed so that

\begin{equation*} \sigma_1\geq \sigma_2\geq \cdots \geq 0. \end{equation*}

A unit eigenvector of \(A^TA\) is a right singular vector of \(A\text{.}\) The number \(\sigma_i\) is the stretch factor in that input direction.

🔗

Activity 6.3.1. A Small Stretch Computation.

Let

\begin{equation*} A= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}

Let

\begin{equation*} \mathbf{e}_1= \begin{bmatrix} 1\\ 0 \end{bmatrix}, \qquad \mathbf{e}_2= \begin{bmatrix} 0\\ 1 \end{bmatrix}. \end{equation*}

🔗

Compute \(A\mathbf{e}_1\) and \(A\mathbf{e}_2\text{.}\)
🔗

🔗
Compute \(\|A\mathbf{e}_1\|\) and \(\|A\mathbf{e}_2\|\text{.}\)
🔗

🔗
Compute \(A^TA\text{.}\)
🔗

🔗
Find the eigenvalues of \(A^TA\text{.}\)
🔗

🔗
What are the singular values of \(A\text{?}\)
🔗

🔗
Which unit direction is stretched most?
🔗

🔗

Solution.

We have

\begin{equation*} A\mathbf{e}_1= \begin{bmatrix} 3\\ 0 \end{bmatrix}, \qquad A\mathbf{e}_2= \begin{bmatrix} 0\\ 1 \end{bmatrix}. \end{equation*}

Thus

\begin{equation*} \|A\mathbf{e}_1\|=3, \qquad \|A\mathbf{e}_2\|=1. \end{equation*}

Also

\begin{equation*} A^TA= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}^T \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix} = \begin{bmatrix} 9 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}

The eigenvalues of \(A^TA\) are \(9\) and \(1\text{.}\) Therefore the singular values of \(A\) are

\begin{equation*} \sigma_1=3, \qquad \sigma_2=1. \end{equation*}

The direction \(\mathbf{e}_1\) is stretched most. This is the simplest version of the question

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|. \end{equation*}

🔗

Activity 6.3.2. Reading the same stretch in code.

The following code repeats the previous activity using \(A^TA\text{.}\)

🔗

import numpy as np

A = np.array([[3., 0.],
              [0., 1.]])

B = A.T @ A
eigvals, eigvecs = np.linalg.eigh(B)

singular_values = np.sqrt(eigvals[::-1])
dominant_direction = eigvecs[:, -1]

B, eigvals, singular_values, dominant_direction

Output:

🔗

(array([[9., 0.],
        [0., 1.]]),
 array([1., 9.]),
 array([3., 1.]),
 array([1., 0.]))

What mathematical matrix is stored in B?
🔗

🔗
Why are the entries of eigvals squared stretch factors?
🔗

🔗
Why does the code take a square root?
🔗

🔗
Why does eigvecs[:, -1] give the most-stretched input direction?
🔗

🔗
What value of \(\max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|\) does the code predict?
🔗

🔗

Solution.

The matrix B is \(A^TA\text{.}\) The entries of eigvals are eigenvalues of \(A^TA\text{,}\) so they are values of \(\|A\mathbf{x}\|^2\) for special unit input directions. The code takes a square root because singular values measure \(\|A\mathbf{x}\|\text{,}\) not \(\|A\mathbf{x}\|^2\text{.}\) The command np.linalg.eigh lists eigenvalues in increasing order, so the largest eigenvalue is last, and eigvecs[:, -1] is its eigenvector. The largest singular value is \(3\text{,}\) so

\begin{equation*} \max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|=3. \end{equation*}

🔗

The next section packages these ingredients into one factorization. The right singular vectors are special input directions. The singular values are stretch factors. Multiplying a right singular vector by \(A\) gives the corresponding output direction.

🔗

Prev Top Next