MATH347 L25: SVD applications

• New concepts:

  • The reduced SVD

  • Solving linear algebra problems through the SVD

  • The pseudo-inverse of a matrix

  • Image compression

The reduced SVD

• The SVD states: for $𝑨\in {ℝ}^{m\times n}$, $\exists 𝑼\in {ℝ}^{m\times m}$, $\exists 𝑽\in {ℝ}^{n\times n}$ orthogonal, $𝚺\in {ℝ}_{+}^{m\times n}$ pseudodiagonal such that $𝑨=𝑼𝚺{𝑽}^T$

• Recall that $𝚺=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r,0,\dots ,0)$ with $r=\mathrm{rank}\left(𝑨\right)⩽min(m,n)$

• The rank-1 expansion of $𝑨$ states

  ${\displaystyle 𝑨=\sum _{j=1}^r{\sigma }_j{𝒖}_j{𝒗}_j^T}$

  which can be expressed as the matrix multiplication

  ${\displaystyle 𝑨={𝑼}_r{𝚺}_r{𝑽}_r^T}$

  known as the reduced SVD with ${𝑼}_r\in {ℝ}^{m\times r}$, ${𝑽}_r\in {ℝ}^{n\times r}$, ${𝚺}_r\in {ℝ}_{+}^{r\times r}$

  ${\displaystyle {𝑼}_r=\left[\begin{array}{lll}{𝒖}_1& \dots & {𝒖}_r\end{array}\right],{𝑽}_r=\left[\begin{array}{lll}{𝒗}_1& \dots & {𝒗}_r\end{array}\right],{𝚺}_r=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r),}$

  and $C\left(𝑨\right)=C\left({𝑼}_r\right)$, $C\left({𝑨}^T\right)=C\left({𝑽}_r\right)$, i.e., columns of ${𝑼}_r,{𝑽}_r$ are bases for the column, row spaces of $𝑨$, respectively.

Solving linear algebra problems: linear systems

• Solving a linear system: $𝑨𝒙=𝒃$, with $𝒃\in C\left(𝑨\right)$, $𝑨\in {ℝ}^{m\times n}$, $𝑨=𝑼𝚺{𝑽}^T$

  ${\displaystyle (𝑼𝚺{𝑽}^T)𝒙=𝒃\Rightarrow 𝚺𝒚=𝒛,\mathrm{with}𝒚={𝑽}^T𝒃\in {ℝ}^n,𝒛={𝑼}^T𝒃\in {ℝ}^m}$

  Components

  ${\displaystyle \left[\begin{array}{lllllll}{\sigma }_1& & & & & & \\ & {\sigma }_2& & & & & \\ & & \ddots & & & & \\ & & & {\sigma }_r& & & \\ & & & & 0& & \\ & & & & & \ddots & \\ & & & & & & 0\end{array}\right]\left[\begin{array}{l}{y}_1\\ y_2\\ ⋮\\ y_r\\ y_{r+1}\\ ⋮\\ y_n\end{array}\right]=\left[\begin{array}{l}{z}_1\\ z_2\\ ⋮\\ z_r\\ 0\\ ⋮\\ 0\end{array}\right].}$

  Note that $𝒃\in C\left(𝑨\right)$ implies that $𝒃$ can be expressed as the $r$ basis vectors ${𝒖}_1,\dots ,{𝒖}_r$. From the above deduce that $y_j=z_j/{\sigma }_j$, with $n-r$ arbitrary parameters $y_{r+1},\dots ,y_n$. This corresponds to the FTLA since $n-r$ is the nullity of $𝑨$.

Solving linear algebra problems: linear systems

• Express above as a matrix multiplication

  ${\displaystyle 𝒚=\left[\begin{array}{l}{y}_1\\ y_2\\ ⋮\\ y_r\\ y_{r+1}\\ ⋮\\ y_n\end{array}\right]=\left[\begin{array}{lllllll}{\sigma }_1^{-1}& & & & & & \\ & {\sigma }_2^{-1}& & & & & \\ & & \ddots & & & & \\ & & & {\sigma }_r^{-1}& & & \\ & & & & 0& & \\ & & & & & \ddots & \\ & & & & & & 0\end{array}\right]\left[\begin{array}{l}{z}_1\\ z_2\\ ⋮\\ z_r\\ 0\\ ⋮\\ 0\end{array}\right]={𝚺}^{+}𝒛.}$

• Obtain the solution to the linear system $𝑨𝒙=𝒃$ as

  ${\displaystyle 𝒙=(𝑽{𝚺}^{+}{𝑼}^T)𝒃={𝑨}^{+}𝒃}$

  with ${𝑨}^{+}\in {ℝ}^{n\times m}$

Solving linear algebra problems: least squares

• Consider now $𝒃\notin C\left(𝑨\right)$ and the least squares problem ${min}_{𝒙}||𝒃-𝑨𝒙||$.

• FTLA: $𝒃$ has a part within $C\left(𝑨\right)$ (perhaps zero) and a part within $N\left({𝑨}^T\right)$

  ${\displaystyle 𝒃=𝒚+𝒛,𝒚\in C\left(𝑨\right),𝒛\in N\left({𝑨}^T\right)}$

• The SVD furnishes orthonormal bases for $C\left(𝑨\right)$ and $N\left({𝑨}^T\right)$

  ${\displaystyle 𝒚=\left[\begin{array}{lll}{𝒖}_1& \dots & {𝒖}_r\end{array}\right]𝒔={𝑼}_r𝒔,𝒛=\left[\begin{array}{lll}{𝒖}_{r+1}& \dots & {𝒖}_m\end{array}\right]𝒕={𝑼}_{m-r}𝒕}$

  with $𝒔\in {ℝ}^r$, $𝒕\in {ℝ}^{m-r}$

• The orthogonal projection of $𝒃$ onto $C\left(𝑨\right)$ is $𝒚={𝑼}_r{𝑼}_r^T𝒃$. Obtain:

  ${\displaystyle 𝑨𝒙=({𝑼}_r{𝚺}_r{𝑽}_r^T)𝒙={𝑼}_r{𝑼}_r^T𝒃\Rightarrow }$ ${\displaystyle 𝒙=({𝑽}_r{𝚺}_r^{+}{𝑼}_r^T)𝒃=(𝑽{𝚺}^{+}{𝑼}^T)𝒃={𝑨}^{+}𝒃,}$

  same as for linear systems.

Pseudo-inverse

Definition. For $𝑨\in {ℝ}^{m\times n}$ with SVD $𝑨=𝑼𝚺{𝑽}^T$ the pseudoinverse of $𝑨$ is defined as ${𝑨}^{+}=𝑽{𝚺}^{+}{𝑼}^T$ with

• Solutions to both linear systems and least squares problems can be succintly stated through the pseudoinverse

  ${\displaystyle 𝒙={𝑨}^{+}𝒃.}$

• In general, the most direct approach to establishing some result about a matrix is to consider its SVD.

Reduced description by truncation of covariance matrix SVD

• SVDs: $𝑿=𝑼𝚺{𝑽}^T$, $C_{𝑿}={𝑿}^T𝑿=𝑽𝚲{𝑽}^T$, $𝚲={𝚺}^T𝚺$

• Take first $q$ column vectors of $𝑽$, ${𝑽}_q=\left[\begin{array}{lll}{𝒗}_1& \dots & {𝒗}_q\end{array}\right]$, $q<n$

  ${\displaystyle 𝒙={𝑽}_q𝒖=\left[\begin{array}{cccc}{𝒗}_1& {𝒗}_2& \dots & {𝒗}_q\end{array}\right]𝒖.}$

• System description in terms of $𝒖\in {ℝ}^q$ is more economical than that in terms of $𝒙\in {ℝ}^n$

• In image compression, successive pixel columns are correlated and reduced descriptions are possible