"Maymester MATH547 Linear Algebra for Applications in Data Science"

1.MATH547 Homework 3

Topic:	Math@UNC environment
Post date:	May 20, 2020
Due date:	May 21, 2020

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}}$ .

Is ${𝒇 (𝒖_{1}), \dots, 𝒇 (𝒖_{n})}$ a basis for $𝒱$ ?
If $nullity (𝒇) = 0$ must $m = n$ ?
If $m = n$ and $𝒖_{i} = 𝒗_{i}$ for $i = 1, \dots, m$ , what is the matrix $𝑨$ representing $𝒇$ ?
Determine the singular value decomposition and pseudo-inverse of a matrix $𝑨 \in ℝ^{1 \times n}$ (i.e., a row vector).

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.

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.

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^{2 q}$ . The image is thus specified as a linear combination of the columns of the identity matrix $𝑰 \in ℝ^{m \times m}$ ,

𝒃 = 𝑰 𝒃 = b_{1} 𝒆_{1} + b_{2} 𝒆_{2} + \dots + b_{m} 𝒆_{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} \overset{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

C (2^{m}, m) = \frac{2^{m}!}{m! (2^{m} - m)!}, m = 16 \Rightarrow C (2^{16}, 16) = \frac{2^{16}!}{16! (2^{16} - 16)!} ≅ 5.5 \times 10^{63} .

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

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?

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 = 2 q, 2 q - 2, 2 q - 4, 2 q - 6, 2 q - 8$ .

1.3.5.Images as mappings

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

𝑨 = 𝑨 𝑰 = 𝑨 [\begin{array}{cccc} 𝒆_{1} & 𝒆_{2} & \dots & 𝒆_{m} \end{array}] = [\begin{array}{cccc} 𝑨 𝒆_{1} & 𝑨 𝒆_{2} & \dots & 𝑨 𝒆_{m} \end{array}],

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

𝑨_{k} = \sum_{l = 1}^{k} σ_{l} 𝒖_{l} 𝒗_{l}^{T} .

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

1.3.6.Extracting and applying motifs

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

𝑨 = 𝑺 𝚲 𝑻^{T}, 𝑩 = 𝑼 𝚺 𝑽^{T} .

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

𝑪 = \sum_{l = 1}^{min (k, q)} λ_{l} 𝒔_{l} 𝒕_{l}^{T} + \sum_{l = max (1, r - k)}^{r} σ_{l} 𝒖_{l} 𝒗_{l}^{T},

for $k = m / 2, m / 4, m / 8, m / 16$ where $r = rank (𝑩)$ .