Sources: - [[Data-Driven Science and Engineering]] - https://www.youtube.com/watch?v=nbBvuuNVfco # Notes - Denoted as SVD - Guaranteed to exist - Applications - Dimensionality reduction - Solving linear systems $\mathbf{Ax}=\mathbf{b}$ - Compute pseudo-inverse of non-square matrices - [[Principal Component Analysis]] - De-noising data - Generalizes concept of the Fast Fourier Transform - See also: - [[Economy SVD]] # Definition $ \mathbf{X}=\mathbf{U\Sigma V^*\approx\tilde{\mathbf{U}}}\tilde{\mathbf{\Sigma}}\tilde{\mathbf{V}}^* $ - Matrix $\mathbf{X}\in\mathbb{C}^{n\times m}$ - *rank* of $\mathbf{X}$ given by number of non-zero singular values in $\mathbf{\Sigma}$ - examples - faces - each column is reshaped vector of image pixels - reshaped from 2D matrix in to column vector - $m\times n$ - $m$ number of pixels - $n$ number of faces - fluid flow - $m$ flow data reshaped into column vector - $n$ timesteps as flow evolves - Matrix $\mathbf{U}\in\mathbb{C}^{n\times m}$, [[Unitary matrix|unitary]] - orthogonal - columns called *left singular vectors* - eigenvectors - $u_1$ (left-most singular vector) most dominant eigenvector - Matrix $\mathbf{\Sigma}\in\mathbb{C}^{n\times m}$ - contains decreasing, non-negative diagonal entries - called *singular values* - Matrix $\mathbf{V}\in\mathbb{C}^{n\times m}$, unitary - orthogonal - columns called *right singular vectors* ## The Data Set Let $\mathbf{X}$ be a $m\times n$ dimension matrix consisting of column vectors $\mathbf{x}_k$ of length $n$: $ \mathbf{X}= \begin{bmatrix} \vert & \vert & & \vert \\ \mathbf{x}_1 & \mathbf{x}_2 & \dots & \mathbf{x}_m \\ \vert & \vert & & \vert \end{bmatrix} $ Each $\mathbf{x}_k$ is an individual measurement of a state, reshaped into a column vector. These states can manifest themselves as: - pixels in an image - a physical system, such as the velocity of a fluid system at a set of points - neural measurements from a brain - etc. Many of these examples evolve in time, implying that $\mathbf{x}_k=\mathbf{x}(k\Delta t)$. The length of these vectors $n$ is referred to as the *state dimension*, and is typically on the order of millions to billions of degrees of freedom. Since each column represents the system at a specific point in time, they are referred to as *snapshots*, and there will be $m$ snapshots in $\mathbf{X}$. Matrices with $n\gg m$ are called *tall-skinny*, and those with $n\ll m$ are called *short-fat*. # Computing 1. Reduce $\mathbf{X}$ to an upper triangular matrix - QR factorization 2. Reduce upper triangular matrix into bidiagonal form - Householder reflections # Matrix Approximation Can express $\mathbf{X}$ as a sum of rank-one matrices known as the dyadic summation: $ \mathbf{X}=\sum_{k=1}^m\sigma_k\mathbf{u}_k\mathbf{v}_k^*=\sigma_1\mathbf{u}_1\mathbf{v}_1^*+\sigma_2\mathbf{u}_2\mathbf{v}_2^*+\dots+\sigma_m\mathbf{u}_m\mathbf{v}_m^* $ Because the singular values $\sigma_k$ are in decreasing order, each rank-one matrix is less important the previous. This decrease is often rapid, so truncating at some rank $r$ can yield a good approximation: $ \mathbf{X}\approx\tilde{\mathbf{X}}=\sum_{k=1}^m\sigma_k\mathbf{u}_k\mathbf{v}_k^*=\sigma_1\mathbf{u}_1\mathbf{v}_1^*+\sigma_2\mathbf{u}_2\mathbf{v}_2^*+\dots+\sigma_r\mathbf{u}_r\mathbf{v}_r^* $ The truncated SVD is then represented by: $ \tilde{\mathbf{X}}=\tilde{\mathbf{U}}\tilde{\mathbf{\Sigma}}\tilde{\mathbf{V}}^* $ where $\tilde{\mathbf{U}}$ and $\tilde{\mathbf{V}}$ contain the first $r$ columns of $\mathbf{U}$ and $\mathbf{V}$, and $\tilde{\mathbf{\Sigma}}$ contains the first $r\times r$ sub-block of $\mathbf{\Sigma}$. Error associated with this truncation can be approximated with the [[Eckart-Young theorem]]