1.MATH547 Homework 3

1.1.Background

This homework investigates consequences of the fundamental theorem of algebra and application of the singular value decomposition.

1.2.Theoretical questions

Consider a linear mapping $𝒇:U\to V$, from vector space $𝒰=(U,ℝ,+,\cdot )$ with basis $\{{𝒖}_1,\dots ,{𝒖}_n\}$, to $𝒱=(V,ℝ,+,\cdot )$, with basis $\{{𝒗}_1,\dots ,{𝒗}_m\}$.

1. Is $\{𝒇\left({𝒖}_1\right),\dots ,𝒇\left({𝒖}_n\right)\}$ a basis for $𝒱$?

   Solution. Not necessarily, for example if $𝒇\left({𝒖}_j\right)=𝟎$.

2. If $\mathrm{nullity}\left(𝒇\right)=0$ must $m=n$?

   Solution. No. Let $𝑨\in {ℝ}^{m\times n}$ be matrix associated with $𝒇$. If $\mathrm{nullity}\left(𝒇\right)=0$ then $N\left(𝑨\right)=\left\{𝟎\right\}$, and the only solution to $𝒇\left(𝒙\right)=𝟎$ is $𝒙=𝟎$. Consider $𝒇:ℝ\to {ℝ}^2$,$𝒇\left(x\right)={\left[\begin{array}{cc}x& 2x\end{array}\right]}^T=𝑨x$, with $𝑨={\left[\begin{array}{cc}1& 2\end{array}\right]}^T$, and $m=1$, $n=2$, $m\ne n$.

3. If $m=n$ and ${𝒖}_i={𝒗}_i$ for $i=1,\dots ,m$, what is the matrix $𝑨$ representing $𝒇$?

   Solution. The identity matrix $𝑨=𝑰$. Apply the linear mapping $𝒗=𝒇\left(𝒖\right)=𝑨𝒖$ to the basis vectors $\{{𝒖}_1,\dots ,{𝒖}_m\}$, to obtain

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

   Since $𝑼$ is a basis, the column vectors are linearly independent and the matrix is invertible,

   ${\displaystyle 𝑨=𝑽{𝑼}^{-1}.}$

   The statement ${𝒖}_i={𝒗}_i$ can be interpreted in one of two ways (these descriptions are said to be duals of one another, and distinguish between a vector as a geometrical entity and its coordinates in some given basis):

   1. ${𝒖}_i$ is a vector that contains the coordinates of the $i^{\mathrm{th}}$ basis vector of $U$ in the $𝑰$ basis, ${𝒖}_i=𝑰{𝒖}_i$. Similarly, ${𝒗}_i$ is a vector that contains the coordinates of the $i^{\mathrm{th}}$ basis vector of $V$ in the $𝑰$ basis, ${𝒗}_i=𝑰{𝒗}_i$. In this case ${𝒖}_i={𝒗}_i$ implies $𝑼=𝑽$, and $𝑨=𝑰$. This interpretation was emphasized in this course, and is appropriate for $U=V={ℝ}^m$.

   2. ${𝒖}_i$ is the $i^{\mathrm{th}}$ basis vector of $U$, whose coordinates in that basis are ${𝒃}_i$ given by ${𝒖}_i=𝑼{𝒃}_i$. Similarly ${𝒗}_i=𝑽{𝒄}_i$. The statement ${𝒖}_i={𝒗}_i$ now implies $𝑼{𝒃}_i=𝑽{𝒄}_i$, such that

      ${\displaystyle {𝒄}_i={𝑽}^{-1}𝑼{𝒃}_i}$

      and the matrix associated with the mapping would be $𝑨={𝑽}^{-1}𝑼$. This interpretation is appropriate when mapping between different vector spaces of the same dimension, $U\ne V$, $\dim \left(U\right)=\dim \left(V\right)$.

4. Determine the singular value decomposition and pseudo-inverse of a matrix $𝑨\in {ℝ}^{1\times n}$ (i.e., a row vector).

   Solution. The SVD is $𝑨=𝑼𝚺{𝑽}^T$, $𝑼\in {ℝ}^{m\times m}$ orthogonal, $𝑽\in {ℝ}^{n\times n}$ orthogonal, $𝚺\in {ℝ}_{+}^{m\times n}$ diagonal. For $𝑨$ a row vector, $m=1$, and

   ${\displaystyle 𝚺=\left[\begin{array}{cccc}{\sigma }_1& 0& \dots & 0\end{array}\right]}$

   with ${\sigma }_1={||𝑨||}_2$. By definition of the matrix $2$-norm

   ${\displaystyle {\sigma }_1={sup}_{||𝒙||=1}||𝑨𝒙||.}$

   Since $𝑨={𝒂}^T$,

   ${\displaystyle 𝑨𝒙={𝒂}^T𝒙=\sum _{i=1}^n{a}_i{x}_i,\sum _{i=1}^n{x}_i^2=1.}$

   The largest possible value of $||𝑨𝒙||$ when $||𝒙||=1$, is ${\sigma }_1=||𝑨||={max}_{1⩽i⩽n}\left|a_i\right|$. The SVD is

   ${\displaystyle 𝑨=\left[1\right]\left[\begin{array}{cccc}{\sigma }_1& 0& \dots & 0\end{array}\right]\left[\begin{array}{c}\frac{{𝒂}^T}{{\sigma }_1}\\ {𝑽}_{n-1}^T\end{array}\right]}$

   with ${𝑽}_{n-1}^T𝒂=0$, ${𝑽}_{n-1}^T{𝑽}_{n-1}={𝑰}_{n-1}$ (orthogonal).

1.3.Ordered bases for the fundamental spaces and painting motifs

The fudamental theorem of linear algebra partitions the domain and codomain of a linear mapping. The singular value decomposition provides orthogonal bases for each of the subspaces arising in the partition. The bases are ordered according to the amplification behavior of the linear mapping, expressed through the norm of successive restrictions of the mapping. This approach is closely aligned with typical problems in data science, and can be used in a variety of scenarios. In this homework linear algebra methods will first be used in a field far removed from the physical sciences: extracting the quirks of painter style from the overall composition of a painting, and applying one artist's style to another artist's composition. This is often-encountered data science problem: distinguishing between small and large scale features of data.

First steps in solving the homework questions will be carried out in class. Each of the following subsections is a homework question, with 1 grade point awarded for a correct solution. Here are some initial Octave instructions to define a directory to save images into and define a function to read an image.

octave] 

cd homework; mkdir hw03; cd hw03

octave] 

im=imread("/home/student/courses/MATH547ML/data/paintings/Andy_Warhol_127.jpg");

octave] 

imshow(im)

octave] 

function im=pread(name)
  im=imread(strcat("/home/student/courses/MATH547ML/data/paintings/",name));
  im=rgb2gray(im);
end

octave] 

im=pread("Andy_Warhol_127.jpg");

octave] 

imshow(im); size(im)

octave] 

1.3.1.Data input mappings

Define a linear mapping that rescales data within an image file to some specified size $p_x\times p_y$ . Determine whether the mapping is data-preserving, and if not, quantify the amount of data loss.

Solution. One such linear mapping is to simply take a portion of the image. If the initial image was $q_x\times q_y$ the data loss is $q_x\times q_y-p_x\times p_y$.

octave] 

function im1=psize(im0,px,py)
  [mx,my]=size(im0);
  cx=floor(mx/2); cy=floor(my/2);
  px2=floor(px/2); py2=floor(py/2);
  im1 = im0(cx-px2:cx+px2,cy-py2:cy+py2);
end

octave] 

imshow(psize(im,256,256))

octave] 

imshow(psize(pread("Vincent_van_Gogh_167.jpg"),256,256))

octave] 

1.3.2.Images as data: change of basis

Take the largest possible portion of a painting of size $p\times p$ with $p=2^q$. Interpret the resulting image as a vector $𝒃\in {ℝ}^m$ with $m=p^2=2^{2q}$. The image is thus specified as a linear combination of the columns of the identity matrix $𝑰\in {ℝ}^{m\times m}$,

and describes illumination on a pixel-by-pixel basis. A column vector of $𝑰$ can be interpreted as the binary base representation of a natural number from the set $P=\{1,2,3,\dots ,2^m\}$, namely $2^{j-1}\stackrel{g}{\to }{𝒆}_j$.

Note that is one choice among the possible combinations of $m$ objects chosen from a set with $2^m$ elements, $C(2^m,m)$. Even for small $m$, the number of choices is enormous

Construct a new basis by random choice of numbers from $P$ and the $g$ mapping. Check if the basis is orthogonal.

Solution. Let $M$ be the largest representable integer on a computer. If $M<m=p^2$ then the binary number representation would not construct a basis since the vector $𝒖$ associated with binary number $B_{𝒖}>M$ is not within span$\{{𝒗}_1,\dots ,{𝒗}_m\}$ associated with binary numbers $\{B_1,\dots ,B_m\}$, all less than $M$, $B_i⩽M$. Choose $m<M$. Orthgonality of vectors associated with binary numbers $B_i,B_j$ corresponds to a zero result from the bitwise and operation.

octave] 

m=4*4;

octave] 

B=randi(flintmax()-1,m,1);

octave] 

C=zeros(m,m);
for i=1:m
  for j=1:m
    C(i,j)=bitand(B(i),B(j));
  end;
end

octave] 

max(max(C))

octave] 

Linear dependence is the same as equality in this binary representation.

octave] 

D=zeros(m,m);
for i=1:m
  for j=i+1:m
    D(i,j) = B(i)==B(j);
  end;
end

octave] 

max(max(D))

octave] 

From above, a non-orthogonal basis is obtained.

1.3.3.Images as data: positive checkerboard basis

Construct another basis that corresponds to successive halving of image regions by factors $(2^k,2^l)$ along the horizontal and vertical dimensions. Are basis vectors orthogonal?

Solution. There are many possible approaches to this problem. In the following a full solution is presented highlighting that application of linear algebra concepts to practical data science problems usually involves non-trivial preprocessing of the data. Since the solution does involve considerable technique from outside of linear algebra full credit is awarded to all attempts of this problem.

First consider the simplest possible case. A $1\times 1$ image cannot be halved, hence start with $2\times 2$ images for which

give 6 possible patterns encoded by row vectors

Only four basis vectors are required and can be chosen as

octave] 

B=[1 0 1 0; 0 1 0 1; 1 1 0 0; 0 0 1 1; 1 0 0 1; 0 1 1 0];
C=[1 0 1 0; 1 1 0 0; 0 1 1 0; 0 0 1 1];

octave] 

[rank(B) rank(C)]

octave] 

The pattern suggested by above is alternating groups of $n$ 1's and $n$ 0's, that are then shifted right by $1,\dots ,n$ places. Define a function to generate alternating 1,0 bit groupings for images of size $m=p\times p$, $p=2^q$. There are $2^{2q-1}$ such numbers.

octave] 

q=2; p=2^q; m=p^2; disp([q p m])

octave] 

g=zeros(2^(2*q-1),1); o=2^m-1;
for i=0:q
  k=2^i; l=2^k; disp([k l]);
  g(i+1) = bitshift(l-1,2^i);
  dec2bin(g(i+1))
end

octave] 

1.3.4.Images as data: mixed-sign checkerboard basis

Map the binary digits $\{0,1\}$ from the positive checkerboard basis to integers $\{-1,1\}$. Check if the newly obtained basis is orthogonal. Display approximations of the image that result from the first $2^l$ basis vectors, $l=2q,2q-2,2q-4,2q-6,2q-8$.

Solution. As above, s.ince the solution does involve considerable technique from outside of linear algebra full credit is awarded to all attempts of this problem.

1.3.5.Images as mappings

Alternatively, an image can be interpreted as a matrix $𝑨$, hence a mapping. From

the image can be interpreted as the transformation of the image encoded by $𝑰$. Denote by ${𝑨}_k$ the $k^{\mathrm{th}}$-rank approximation of $𝑨$ from the singular value decomposition $𝑨=𝑼𝚺{𝑽}^T$

Display the images that correspond to $k=m,m/2,m/4,m/8$.

Solution. Construct and represent each ${𝑨}_k$.

octave] 

function im=svdim(S,U,V,p)
  im=S(1,1)*U(:,1)*V(:,1)';
  for k=2:p
    im=im+S(k,k)*U(:,k)*V(:,k)';
  end;
end

octave] 

figure(3); clf; imshow(im)

octave] 

[U,S,V]=svd(im,1);

octave] 

figure(2); plot(log10(diag(S)),'o');

octave] 

figure(1); clf; imagesc(svdim(S,U,V,10)); colormap(gray); print -deps HW03Fig01.eps

octave] 

figure(1); clf; imagesc(svdim(S,U,V,20)); colormap(gray); print -deps HW03Fig02.eps

octave] 

figure(1); clf; imagesc(svdim(S,U,V,40)); colormap(gray); print -deps HW03Fig03.eps

octave] 

1.3.6.Extracting and applying motifs

Consider images from two different artists, $𝑨,𝑩$ and their singular value decompositions

Let $q=\mathrm{rank}\left(𝑨\right)$, $r=\mathrm{rank}\left(𝑩\right)$. Construct and display images that take the large scale features from $𝑨$ combined with small scale features from $𝑩$,

for $k=m/2,m/4,m/8,m/16$where $r=\mathrm{rank}\left(𝑩\right)$.

Solution. Choose first $40$ modes from the composition image, and mmodes 50 to 60 from the style image.

octave] 

ims=pread("Vincent_van_Gogh_50.jpg");

octave] 

figure(4); imshow(ims)

octave] 

imC=psize(im,256,256); imS=psize(ims,256,256);

octave] 

figure(1); clf; imshow(imC); print -deps Hw03Fig04.eps;

octave] 

figure(2); clf; imshow(imS); print -deps HW03Fig05.eps;

octave] 

[Uc,Sc,Vc]=svd(imC,1); [Us,Ss,Vs]=svd(imS,1);

octave] 

function im=svdimpq(S,U,V,p,q)
  im=S(p,p)*U(:,p)*V(:,p)';
  for k=p+1:q
    im=im+S(k,k)*U(:,k)*V(:,k)';
  end;
end

octave] 

imCS = svdim(Sc,Uc,Vc,40) + svdimpq(Ss,Us,Vs,50,60);

octave] 

figure(5); clf; imagesc(imCS); colormap(gray); print -deps Hw03Fig06.eps;

octave]