27 Positive (Semi)Definite Matrices, Gram Matrices, SVD

Lecture from 18.12.2024 | Video: Videos ETHZ

This lecture explores the properties of symmetric matrices, leading to the development of the Singular Value Decomposition (SVD). We will begin by reviewing the spectral theorem and the Rayleigh quotient, which provide fundamental insights into the behavior of symmetric matrices. We’ll then move on to positive definite matrices, Gram matrices, and finally arrive at the SVD, a powerful tool for analyzing general matrices.

Symmetric Matrices

From the previous lecture…

Our starting point is the class of real, symmetric matrices. Recall that a matrix $A\in {\mathbb{R}}^{n\times n}$ is symmetric if $A=A^T$.

The Spectral Theorem

Theorem (Spectral Theorem)

Let $A$ be a real $n\times n$ symmetric matrix. Then there exists an orthonormal basis of ${\mathbb{R}}^n$ consisting of eigenvectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ of $A$, with corresponding real eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$. Furthermore, $A$ can be decomposed as:

$A={\sum }_{i=1}^n{\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^T$

Explanation

• Orthonormal Basis: The eigenvectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are mutually orthogonal (their dot products are zero) and have unit length (their norms are 1). They form a basis for ${\mathbb{R}}^n$, meaning any vector in ${\mathbb{R}}^n$ can be expressed as a linear combination of these eigenvectors.
• Decomposition: The spectral theorem states that any symmetric matrix can be expressed as a weighted sum of rank-1 matrices formed by the outer products of its eigenvectors. Each term ${\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^T$ represents a projection onto the direction of the eigenvector ${\mathbf{v}}_i$, scaled by the eigenvalue ${\lambda }_i$.

Note that this follow from:

$\Lambda$ is a diagonal matrix consisting of the eigenvalues (as shown in the last few lectures).

The Rayleigh Quotient

Proposition (Rayleigh Quotient)

Let $A\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix. The Rayleigh Quotient, defined for any non-zero vector $\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$, is given by:

$R(\mathbf{x})=\frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}=\frac{{\mathbf{x}}^{T}A\mathbf{x}}{\Vert \mathbf{x}{\Vert }^2}$

The Rayleigh Quotient $R(\mathbf{x})$ attains its maximum value at $R({\mathbf{v}}_{max})={\lambda }_{max}$ and its minimum value at $R({\mathbf{v}}_{min})={\lambda }_{min}$, where ${\lambda }_{max}$ and ${\lambda }_{min}$ are the largest and smallest eigenvalues of $A$, and ${\mathbf{v}}_{max}$ and ${\mathbf{v}}_{min}$ are their corresponding eigenvectors.

Proof

Since $R({\mathbf{v}}_{max})={\lambda }_{max}$ and $R({\mathbf{v}}_{min})={\lambda }_{min}$, it suffices to show that:

${\lambda }_{min}\le R(\mathbf{x})\le {\lambda }_{max}\text{for all }\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$

From the spectral theorem, we know that for any $\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$, we can express $R(\mathbf{x})$ as: $R(\mathbf{x})=\frac{{\mathbf{x}}^T\left({\sum }_{i=1}^n{\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^T\right)\mathbf{x}}{\Vert \mathbf{x}{\Vert }^2}=\frac{{\sum }_{i=1}^n{\lambda }_i({\mathbf{x}}^T{\mathbf{v}}_i{)}^2}{\Vert \mathbf{x}{\Vert }^2}$

where ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ form an orthonormal basis of eigenvectors of $A$ and ${\lambda }_1,\dots ,{\lambda }_n$ are the associated eigenvalues.

For all $1\le i\le n$, we have:

${\lambda }_{min}({\mathbf{x}}^T{\mathbf{v}}_i{)}^2\le {\lambda }_i({\mathbf{x}}^T{\mathbf{v}}_i{)}^2\le {\lambda }_{max}({\mathbf{x}}^T{\mathbf{v}}_i{)}^2$

Summing over all $i$, we get:

${\lambda }_{min}{\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2\le {\sum }_{i=1}^n{\lambda }_i({\mathbf{x}}^T{\mathbf{v}}_i{)}^2\le {\lambda }_{max}{\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2$

Dividing by $||\mathbf{x}|{|}^2$:

${\lambda }_{min}\frac{{\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2}{\Vert \mathbf{x}{\Vert }^2}\le \frac{{\sum }_{i=1}^n{\lambda }_i({\mathbf{x}}^T{\mathbf{v}}_i{)}^2}{\Vert \mathbf{x}{\Vert }^2}\le {\lambda }_{max}\frac{{\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2}{\Vert \mathbf{x}{\Vert }^2}$ Since the ${\mathbf{v}}_i$‘s are orthonormal, the matrix $V$ with the ${\mathbf{v}}_i$‘s as columns is orthogonal. Then, we have: ${\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2=||V\mathbf{x}|{|}^2=||\mathbf{x}|{|}^2$

So:

$\frac{{\sum }_{i=1}^n({\mathbf{x}}^T{\mathbf{v}}_i{)}^2}{\Vert \mathbf{x}{\Vert }^2}=\frac{||\mathbf{x}|{|}^2}{||\mathbf{x}|{|}^2}=1$

Therefore:

${\lambda }_{min}\le R(\mathbf{x})\le {\lambda }_{max}$

This completes the proof.

Interpretation

• The Rayleigh quotient provides a way to estimate the eigenvalues of a symmetric matrix without explicitly computing them.
• It shows that the eigenvalues of a symmetric matrix can be characterized as the stationary values of the Rayleigh quotient.

Positive Definite Matrices

Positive definite and positive semidefinite matrices are special types of symmetric matrices that arise frequently in various fields, including optimization, statistics, mechanics, and machine learning. They possess unique properties that make them particularly useful for characterizing quadratic forms, defining inner products, and ensuring the convexity of functions.

Definition (Positive Definite and Positive Semidefinite)

A symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is said to be:

• Positive Semidefinite (PSD) if all its eigenvalues are non-negative (i.e., ${\lambda }_i\ge 0$ for all $i$).
• Positive Definite (PD) if all its eigenvalues are strictly positive (i.e., ${\lambda }_i>0$ for all $i$).

Intuition

• Think of a symmetric matrix $A$ as defining a quadratic form $q(\mathbf{x})={\mathbf{x}}^{T}A\mathbf{x}$. If $A$ is PSD, the quadratic form is always non-negative. If $A$ is PD, the quadratic form is always positive, except when $\mathbf{x}$ is the zero vector.

• Geometrically, a PD matrix corresponds to an ellipsoid that is stretched along its principal axes (the eigenvectors of $A$), with the lengths of the semi-axes determined by the eigenvalues. A PSD matrix corresponds to an ellipsoid that might be flattened in some directions (where the eigenvalues are zero).

Positive Definite Matrices and Minima... (MIT)

Proposition: Alternative Characterization of PSD and PD Matrices

The following proposition provides an alternative way to define PSD and PD matrices, which is often easier to work with than the eigenvalue definition.

• A symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is PSD if and only if ${\mathbf{x}}^{T}A\mathbf{x}\ge 0$ for all $\mathbf{x}\in {\mathbb{R}}^n$.
• A symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is PD if and only if ${\mathbf{x}}^{T}A\mathbf{x}>0$ for all $\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$ (i.e., for all non-zero vectors $\mathbf{x}$).

Proof

These statements follow directly from the Rayleigh quotient. Recall that the Rayleigh quotient is defined as:

$R(\mathbf{x})=\frac{{\mathbf{x}}^{T}A\mathbf{x}}{{\mathbf{x}}^T\mathbf{x}}$

and that for a symmetric matrix $A$, we have ${\lambda }_{min}\le R(\mathbf{x})\le {\lambda }_{max}$ for all $\mathbf{x}\ne 0$, where ${\lambda }_{min}$ and ${\lambda }_{max}$ are the smallest and largest eigenvalues of $A$, respectively.

Positive Semi Definite

If all eigenvalues of $A$ are non-negative (${\lambda }_i\ge 0$ for all $i$), then ${\lambda }_{min}\ge 0$. Since $R(\mathbf{x})\ge {\lambda }_{min}$, we have $R(\mathbf{x})\ge 0$ for all $\mathbf{x}\ne 0$. This implies ${\mathbf{x}}^{T}A\mathbf{x}\ge 0$ for all $\mathbf{x}\in {\mathbb{R}}^n$ (since ${\mathbf{x}}^T\mathbf{x}=||\mathbf{x}|{|}^2\ge 0$).

Conversely, if ${\mathbf{x}}^{T}A\mathbf{x}\ge 0$ for all $\mathbf{x}\in {\mathbb{R}}^n$, then $R(\mathbf{x})\ge 0$ for all $\mathbf{x}\ne 0$. Since ${\lambda }_{min}$ is the minimum value of $R(\mathbf{x})$, we must have ${\lambda }_{min}\ge 0$, which means all eigenvalues are non-negative.

Positive Definite

If all eigenvalues of $A$ are positive (${\lambda }_i>0$ for all $i$), then ${\lambda }_{min}>0$. Since $R(\mathbf{x})\ge {\lambda }_{min}$, we have $R(\mathbf{x})>0$ for all $\mathbf{x}\ne 0$. This implies ${\mathbf{x}}^{T}A\mathbf{x}>0$ for all $\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$.

Conversely, if ${\mathbf{x}}^{T}A\mathbf{x}>0$ for all $\mathbf{x}\in {\mathbb{R}}^n\setminus \{0\}$, then $R(\mathbf{x})>0$ for all $\mathbf{x}\ne 0$. Since ${\lambda }_{min}$ is the minimum value of $R(\mathbf{x})$, we must have ${\lambda }_{min}>0$, which means all eigenvalues are positive.

Lemma: Sum of PSD Matrices

If $A,B\in {\mathbb{R}}^{n\times n}$ are symmetric and PSD, then $A+B$ is also PSD.

Proof

Let $\mathbf{x}\in {\mathbb{R}}^n$ be an arbitrary vector. Since $A$ and $B$ are PSD, we know that:

• ${\mathbf{x}}^{T}A\mathbf{x}\ge 0$
• ${\mathbf{x}}^{T}B\mathbf{x}\ge 0$

Adding these inequalities, we get:

${\mathbf{x}}^{T}A\mathbf{x}+{\mathbf{x}}^{T}B\mathbf{x}\ge 0$

Using the distributive property of matrix multiplication, we can rewrite this as:

${\mathbf{x}}^T(A+B)\mathbf{x}\ge 0$

Since this holds for all $\mathbf{x}\in {\mathbb{R}}^n$, it follows that $A+B$ is PSD.

A Key Observation: Gram Matrices are PSD

Definition (Gram Matrix)

Given $n$ vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ in ${\mathbb{R}}^m$, let $V\in {\mathbb{R}}^{m\times n}$ be the matrix whose columns are the vectors ${\mathbf{v}}_i$. The Gram matrix of $V$ is defined as the $n\times n$ matrix $G$ where:

$G_{ij}={\mathbf{v}}_i^T{\mathbf{v}}_j$

In matrix notation, the Gram matrix can be expressed as:

$G=V^{T}V$

Interpretation:

• The Gram matrix captures the pairwise inner products (dot products) between the vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$.
• The diagonal entries $G_{ii}={\mathbf{v}}_i^T{\mathbf{v}}_i=||{\mathbf{v}}_i|{|}^2$ represent the squared lengths (norms) of the vectors.

Proposition: Properties of Gram Matrices

Let $A\in {\mathbb{R}}^{m\times n}$. The non-zero eigenvalues of $A^{T}A\in {\mathbb{R}}^{n\times n}$ are the same as the non-zero eigenvalues (!!!) of $A{A}^T\in {\mathbb{R}}^{m\times m}$. Both matrices are also symmetric and PSD.

Proof

Symmetry

$(A^{T}A{)}^T=A^T(A^T{)}^T=A^{T}A$, and $(A{A}^T{)}^T=(A^T{)}^T{A}^T=A{A}^T$. Thus, both $A^{T}A$ and $A{A}^T$ are symmetric.

PSD

For any $\mathbf{x}\in {\mathbb{R}}^n$, we have ${\mathbf{x}}^T(A^{T}A)\mathbf{x}=(A\mathbf{x}{)}^T(A\mathbf{x})=||A\mathbf{x}|{|}^2\ge 0$. This implies that $A^{T}A$ is PSD. Similarly, for any $\mathbf{y}\in {\mathbb{R}}^m$, we have ${\mathbf{y}}^T(A{A}^T)\mathbf{y}=(A^T\mathbf{y}{)}^T(A^T\mathbf{y})=||A^T\mathbf{y}|{|}^2\ge 0$, so $A{A}^T$ is also PSD.

Eigenvalues

Before going to the proof a small thing we need to show is…

Why is $rank(A)=rank(A^T)=rank(A^{T}A)=rank(A{A}^T)$?

1. $rank(A)=rank(A^T)$:

   • The rank of $A$ is equal to the rank of $A^T$ because row operations (used in Gaussian elimination) do not alter the number of linearly independent rows or columns.
   • The pivots in the row echelon form of $A$ correspond to independent rows and columns, and this property remains invariant under transposition.

2. $rank(A)=rank(A^{T}A)$:

   • Use the rank-nullity theorem to argue:

     • Suppose $x\in N(A)$, meaning $Ax=0$. Then:

       $$A^{T}Ax=A^T(Ax)=0.$$

       Thus, $N(A)\subseteq N(A^{T}A)$.

     • Conversely, assume $x\in N(A^{T}A)$, meaning $A^{T}Ax=0$. Then:

       $$x^T{A}^{T}Ax=0⟹\Vert Ax{\Vert }^2=0⟹Ax=0.$$

       Hence, $N(A^{T}A)\subseteq N(A)$.

     • Since $N(A)=N(A^{T}A)$, their nullities are equal, and the ranks are the same:

       $$rank(A)=rank(A^{T}A).$$

3. $rank(A)=rank(A{A}^T)$:

   • Similarly, for $A{A}^T$:

     • If $x\in N(A)$, then $Ax=0⟹A{A}^T(Ax)=0$, so $N(A)\subseteq N(A{A}^T)$.

     • Conversely, if $x\in N(A{A}^T)$, then:

       $$A{A}^{T}x=0⟹x^{T}A{A}^{T}x=0⟹\Vert A^{T}x{\Vert }^2=0⟹A^{T}x=0.$$

       Since $A^{T}x=0⟹Ax=0$, we have $N(A{A}^T)\subseteq N(A)$.

     • Thus, $N(A{A}^T)=N(A)$, and their ranks are equal:

       $$rank(A)=rank(A{A}^T).$$

Combining all the above results, we have:

Now let us continue with the proof…

Proof

Let $r$ be the rank of $A$. We know that:

$rank(A)=rank(A^T)=rank(A^{T}A)=rank(A{A}^T)=r$

$A^{T}A$ and $A{A}^T$ have a complete set of real eigenvalues and orthogonal eigenvectors. Let ${\lambda }_1,...,{\lambda }_r$ be the $r$ non-zero eigenvalues of $A^{T}A$ and ${\mathbf{v}}_1,...,{\mathbf{v}}_r$ the corresponding eigenvectors. Let ${\mu }_1,...,{\mu }_r$ be the $r$ non-zero eigenvalues of $A{A}^T$ and ${\mathbf{w}}_1,...,{\mathbf{w}}_r$ the corresponding eigenvectors.

We have $A^{T}A{\mathbf{v}}_k={\lambda }_k{\mathbf{v}}_k$. Hence, $A{A}^{T}A{\mathbf{v}}_k={\lambda }_{k}A{\mathbf{v}}_k$. Thus, ${\lambda }_k$ is an eigenvalue of $A{A}^T$ with eigenvector $A{\mathbf{v}}_k$.

Similarly, $(A^{T}A)A^T{\mathbf{w}}_i=A^T(A{A}^T{\mathbf{w}}_i)={\mu }_i{A}^T{\mathbf{w}}_i$. This shows that ${\mu }_i$ is an eigenvalue of $A^{T}A$ with eigenvector $A^T{\mathbf{w}}_i$.

Hence, $\{{\mu }_1,\dots ,{\mu }_r\}=\{{\lambda }_1,\dots ,{\lambda }_r\}$.

Implications

• This proposition establishes that Gram matrices are always symmetric and positive semidefinite.
• The connection between the eigenvalues of $A^{T}A$ and $A{A}^T$ will be crucial for the development of the SVD.

What Else Do We Get for PSD Matrices?

Skipped during the lecture, but part of slides…

Proposition (Cholesky Decomposition)

Every symmetric positive semidefinite matrix $M$ is a Gram matrix of an upper triangular matrix $C$. $M=C^{T}C$ is known as the Cholesky Decomposition.

Proof

Since $M$ is symmetric and PSD, by the spectral theorem, there exists an orthogonal matrix $V$ and a diagonal matrix $\Lambda$ with the non-negative eigenvalues of $M$ on the diagonal such that:

$M=V\Lambda V^T$

Define ${\Lambda }^{1/2}$ as the diagonal matrix obtained by taking the square root of each diagonal entry of $\Lambda$. Then:

$M=V{\Lambda }^{1/2}{\Lambda }^{1/2}{V}^T=(V{\Lambda }^{1/2})(V{\Lambda }^{1/2}{)}^T$

Now, consider the $QR$ decomposition of $(V{\Lambda }^{1/2}{)}^T$:

$(V{\Lambda }^{1/2}{)}^T=QR$

where $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. Substituting this into the expression for $M$:

$M=(QR{)}^T(QR)=R^T{Q}^{T}QR=R^{T}R$

Taking $C=R$, we have $M=C^{T}C$, where $C$ is an upper triangular matrix. This establishes the Cholesky decomposition.

Significance:

• The Cholesky decomposition provides an efficient way to factorize a symmetric positive semidefinite matrix.
• It is widely used in numerical linear algebra, optimization, and statistics.

Introduction to Singular Value Decomposition (SVD)

The Singular Value Decomposition (SVD) is a fundamental matrix factorization technique with wide-ranging applications in linear algebra, data analysis, and machine learning. While the spectral theorem provides a powerful decomposition for symmetric matrices, the SVD extends this concept to all matrices, even those that are not square or symmetric.

The Guiding Question: How can we establish a decomposition analogous to the spectral theorem but applicable to general matrices?

Singular Value Decomposition... (MIT)

Motivation: Extending the Spectral Theorem

Recall that the spectral theorem allows us to decompose a symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ as:

$A={\sum }_{i=1}^n{\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^T=V\Lambda V^T$

where ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are orthonormal eigenvectors of $A$, ${\lambda }_1,\dots ,{\lambda }_n$ are the corresponding eigenvalues, $V$ is an orthogonal matrix whose columns are the eigenvectors, and $\Lambda$ is a diagonal matrix of eigenvalues. This decomposition is elegant and insightful, but its limitation is that it only applies to symmetric matrices.

The Problem of Different Dimensions

When dealing with a general matrix $A\in {\mathbb{R}}^{m\times n}$ where $m\ne n$, the concept of eigenvectors and eigenvalues in the traditional sense becomes problematic. The equation $A\mathbf{v}=\lambda \mathbf{v}$ implies that $A$ maps a vector $\mathbf{v}$ from ${\mathbb{R}}^n$ to a scaled version of itself in ${\mathbb{R}}^m$. These spaces have different dimensions, so the notion of an eigenvector being scaled by a constant doesn’t directly apply.

A New Perspective: Mapping Between Bases

Instead of searching for eigenvectors of $A$ directly, let’s consider the possibility of mapping between different orthonormal bases. Suppose we have an orthonormal basis $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\}$ for ${\mathbb{R}}^n$ and another orthonormal basis $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_m\}$ for ${\mathbb{R}}^m$. Could we find a way to relate these bases through the action of $A$?

Ideally, we’d like to find a set of relationships of the form:

$A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$

where ${\sigma }_i$ are scalar values. This equation suggests that $A$ maps each basis vector ${\mathbf{v}}_i$ in ${\mathbb{R}}^n$ to a scaled version of a corresponding basis vector ${\mathbf{u}}_i$ in ${\mathbb{R}}^m$. The scalars ${\sigma }_i$ would represent the “stretching factors” along these corresponding directions.

Leveraging $A^{T}A$ and $A{A}^T$

From our earlier work, we know that for any matrix $A\in {\mathbb{R}}^{m\times n}$, the matrices $A^{T}A$ and $A{A}^T$ are symmetric and positive semidefinite. Moreover, they share the same non-zero eigenvalues. This suggests that we can apply the spectral theorem to these matrices to obtain orthonormal bases for ${\mathbb{R}}^n$ and ${\mathbb{R}}^m$, respectively.

Let’s consider the spectral decompositions:

• $A{A}^T=U\Lambda U^T$, where $U\in {\mathbb{R}}^{m\times m}$ is orthogonal, and $\Lambda$ is a diagonal matrix with the eigenvalues of $A{A}^T$ (which are non-negative).
• $A^{T}A=V{\Lambda }^{\prime }{V}^T$, where $V\in {\mathbb{R}}^{n\times n}$ is orthogonal, and ${\Lambda }^{\prime }$ is a diagonal matrix with the eigenvalues of $A^{T}A$ (also non-negative).

The columns of $U$ and $V$ will serve as our desired orthonormal bases, and the square roots of the non-zero eigenvalues of $A{A}^T$ and $A^{T}A$ will provide the scaling factors ${\sigma }_i$.

Definition: Singular Value Decomposition (SVD)

Let $A\in {\mathbb{R}}^{m\times n}$ be any matrix. A singular value decomposition of $A$ is a factorization of the form:

$A=U\Sigma V^T$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is an orthogonal matrix whose columns are called the left singular vectors of $A$.
• $V\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix whose columns are called the right singular vectors of $A$.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is a diagonal matrix with non-negative entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min \{m,n\}}\ge 0$ on the diagonal, called the singular values of $A$.

We stopped the lecture here, but the following content remained on the slides…

Compact SVD

If $A$ has rank $r$, the SVD can be expressed in a more compact form:

$A=U_r{\Sigma }_r{V}_r^T$

where:

• $U_r\in {\mathbb{R}}^{m\times r}$ contains the first $r$ left singular vectors.
• $V_r\in {\mathbb{R}}^{n\times r}$ contains the first $r$ right singular vectors.
• ${\Sigma }_r\in {\mathbb{R}}^{r\times r}$ is a diagonal matrix containing the first $r$ (non-zero) singular values.

This compact form is often more efficient in practice, as it avoids storing and manipulating unnecessary zero singular values and their corresponding singular vectors.

Properties of the SVD and Connection to $A{A}^T$ and $A^{T}A$

The SVD provides a powerful way to understand the structure of a general matrix $A$ by relating it to the associated symmetric matrices $A{A}^T$ and $A^{T}A$. Let’s explore this connection further.

Suppose $A\in {\mathbb{R}}^{m\times n}$ has an SVD given by $A=U\Sigma V^T$.

Relationship with $A{A}^T$

Consider the product $A{A}^T$:

$A{A}^T=(U\Sigma V^T)(U\Sigma V^T{)}^T=U\Sigma V^{T}V{\Sigma }^T{U}^T=U(\Sigma {\Sigma }^T)U^T$

Since $V$ is orthogonal, $V^{T}V=I$. Also, note that $\Sigma {\Sigma }^T$ is an $m\times m$ diagonal matrix. Let’s examine the structure of $\Sigma {\Sigma }^T$:

• If $m>n$, then $\Sigma {\Sigma }^T$ has the form:

  $$\Sigma {\Sigma }^T=\left[\begin{array}{ccccc}{\sigma }_1^2& & & & \\ & {\sigma }_2^2& & & \\ & & \ddots & & \\ & & & {\sigma }_n^2& \\ & & & & 0\end{array}\right]$$

  where $0$ is a zero matrix of size $(m-n)\times (m-n)$.

• If $m<n$, then $\Sigma {\Sigma }^T$ has the form:

  $$\Sigma {\Sigma }^T=\left[\begin{array}{cccc}{\sigma }_1^2& & & \\ & {\sigma }_2^2& & \\ & & \ddots & \\ & & & {\sigma }_m^2\end{array}\right]$$

• if $m=n$, then $\Sigma {\Sigma }^T$ is simply a diagonal matrix containing ${\sigma }_i^2$ for $i=1,...,n$.

Thus, we can make the following observations:

1. The equation $A{A}^T=U(\Sigma {\Sigma }^T)U^T$ is an eigendecomposition of $A{A}^T$.
2. The left singular vectors of $A$ (columns of $U$) are the eigenvectors of $A{A}^T$.
3. The squares of the singular values of $A$ (diagonal entries of $\Sigma {\Sigma }^T$) are the eigenvalues of $A{A}^T$.
4. If $m>n$, $A$ has $n$ singular values, while $A{A}^T$ has $m$ eigenvalues. The “missing” $m-n$ eigenvalues are zero.

Relationship with $A^{T}A$

Now consider the product $A^{T}A$:

$A^{T}A=(U\Sigma V^T{)}^T(U\Sigma V^T)=V{\Sigma }^T{U}^{T}U\Sigma V^T=V({\Sigma }^T\Sigma )V^T$

Since $U$ is orthogonal, $U^{T}U=I$. Also, note that ${\Sigma }^T\Sigma$ is an $n\times n$ diagonal matrix. Let’s examine the structure of ${\Sigma }^T\Sigma$:

• If $n>m$, then ${\Sigma }^T\Sigma$ has the form:

  $${\Sigma }^T\Sigma =\left[\begin{array}{ccccc}{\sigma }_1^2& & & & \\ & {\sigma }_2^2& & & \\ & & \ddots & & \\ & & & {\sigma }_m^2& \\ & & & & 0\end{array}\right]$$

  where $0$ is a zero matrix of size $(n-m)\times (n-m)$.

• If $n<m$, then ${\Sigma }^T\Sigma$ has the form:

  $${\Sigma }^T\Sigma =\left[\begin{array}{cccc}{\sigma }_1^2& & & \\ & {\sigma }_2^2& & \\ & & \ddots & \\ & & & {\sigma }_n^2\end{array}\right]$$

• if $m=n$, then ${\Sigma }^T\Sigma$ is simply a diagonal matrix containing ${\sigma }_i^2$ for $i=1,...,n$.

We can make the following observations:

1. The equation $A^{T}A=V({\Sigma }^T\Sigma )V^T$ is an eigendecomposition of $A^{T}A$.
2. The right singular vectors of $A$ (columns of $V$) are the eigenvectors of $A^{T}A$.
3. The squares of the singular values of $A$ (diagonal entries of ${\Sigma }^T\Sigma$) are the eigenvalues of $A^{T}A$.
4. If $n>m$, $A$ has $m$ singular values, while $A^{T}A$ has $n$ eigenvalues. The “missing” $n-m$ eigenvalues are zero.

Key Insights

• The SVD provides a direct link between a general matrix $A$ and the symmetric matrices $A{A}^T$ and $A^{T}A$.
• The singular values of $A$ are the square roots of the non-zero eigenvalues of both $A{A}^T$ and $A^{T}A$.
• The left and right singular vectors of $A$ form orthonormal bases for the column space and row space of $A$, respectively.

We’ll look at the SVD proof and other topics next lecture…

Continue here: 28 SVD Theorem and Proof, SVD Abstraction, Pseudoinverse