Posted: 09/15/21

Due: 09/22/21, 11:55PM

Building upon H03, this assigment focuses on operator approximations using the SVD.

1Track 1

1. Transform the MATH661/images/Frida_Kahlo_96.png image, Fig. 1, into a matrix $𝑨$ of gray scale values. Compute the SVD of $𝑨=𝑼𝚺{𝑽}^T$. Define

   ${\displaystyle {𝑨}_p=\sum _{i=1}^p{\sigma }_i{𝒖}_i{𝒗}_i^T.}$

   Represent as images ${𝑨}_p$ for $p=10k,k=1,2,3,4.$ Comment on what you observe.

   Figure 1. Images to be represented as matrices

   Solution.

   Julia (1.6.1) session in GNU TeXmacs

   ∴	using Images, FileIO, ImageIO

   ∴	using Images

   ∴

   Import an image

   ∴	pre="/home/student/courses/MATH661/images/";

   ∴	im=load(pre*"Frida_Kahlo_96.png");

   ∴	im2=load(pre*"Georges_Seurat_3.png");

   ∴

   Convert image to an array of floats, and display the result

   ∴	A=Float64.(im);

   ∴	imshow(A,cmap="gray");

   ∴	B=Float64.(im2);

   ∴

   Compute the SVD of the array of floats obtained from the image

   ∴	U,S,V=svd(A);

   ∴	U2,S2,V2=svd(B);

   ∴	minimum(size(U2))

   $430$

   ∴

   Define a function to sum the first $p$ rank-one updates from an SVD

   ∴	function rsvd(p,U,S,V) B = S[1]*U[:,1]*V[:,1]' for k=2:p B = B + S[k]*U[:,k]*V[:,k]' end return B end;

   ∴	function lsvd(q,U,S,V) r=minimum(size(U)); B = S[r]*U[:,r]*V[:,r]' for k=r-q:r-1 B = B + S[k]*U[:,k]*V[:,k]' end return B end;

   ∴

   Create a matrix with the first 10 rank-one updates, and display it.

   ∴	B=rsvd(50,U,S,V);

   ∴	imshow(B,cmap="gray");

   ∴	C=lsvd(400,U2,S2,V2);

   ∴	imshow(C,cmap="gray");

   ∴	imshow(B+C,cmap="gray");

   ∴

2. Transform the MATH661/images/Georges_Seurat_3.png image, Fig. 1, into a matrix $𝑩$ of gray scale values. Compute the SVD of $𝑩=𝑾𝚲{𝑿}^T$. Let $r=\mathrm{rank}\left(𝑩\right)$. Define

   ${\displaystyle {𝑪}_{p,q}=\sum _{i=1}^p{\sigma }_i{𝒖}_i{𝒗}_i^T+\sum _{i=r-q+1}^r{\lambda }_i{𝒘}_i{𝒙}_i^T.}$

   Represent as images ${𝑪}_{p,q}$ for $p=10k,q=5k,k=1,2,3,4.$ Comment on what you observe.

3. Revisit Problem 2 of H03. Instead of using the built-in least squares solver $𝒙=𝑨\backslash 𝒚$, use the SVD of $𝑨$ to solve the least squares problem as $𝒙={𝑨}^{+}𝒚$.

2Track 2

1. Matrices $𝑨,𝑩\in {ℂ}^{m\times m}$ are unitarily equivalent if $\exists 𝑸$ unitary such that $𝑨=𝑸𝑩{𝑸}^{\ast }$.

   1. Do unitarily equivalent $𝑨,𝑩$ represent the same linear mapping?

   2. Prove: $𝑨,𝑩$ unitarily equivalent implies they have the same singular values.

   3. Is the converse of (b) true?

2. Use the SVD to prove that any $𝑨\in {ℂ}^{m\times m}$ is the limit of a sequence of matrices of full rank.

3. Using the SVD $𝑨=𝑼𝚺{𝑽}^{\ast }$, $𝑨\in {ℂ}^{m\times n}$, define

   ${\displaystyle {𝑨}_p=\sum _{i=1}^p{\sigma }_i{𝒖}_i{𝒗}_i^{\ast },p\in \mathbb{N},p⩽\mathrm{rank}\left(𝑨\right).}$

   Prove

   ${\displaystyle {||𝑨-{𝑨}_p||}_2={inf}_{𝑩\in {ℂ}^{m\times n},\mathrm{rank}\left(𝑩\right)=p}||𝑨-𝑩||.}$

4. Solve Problem 1 & 2, Track 1.