Applied Questions for 1st Year Linear Algebra (feat. SVD)

One quick teaching post. At SUSTech all first year students need to take Linear Algebra. All students, also those who are going to study design or who want to be experimental biologists.

There are several sections. I have the only one in English (with 10 students). Most of the homework is uniform among all sections (which also share the exams), but each week each lecturer can ask 5 additional questions. Most of my students enjoy applications. As we follow one of Gilbert Strang’s books, there are many examples. Today I was preparing the part on the Singular Value Decomposition. Strang mentions image compression as an application. I feel that this is quite cool, but can I make an exercise out of it which is Ok for my students? I am not sure, but today I tried. If my students liked it, I will see in two or three weeks.

The first obstacle is that it should be limited to small matrices, while I need recognizable symbols. The Latin alphabet is surely a good choice. And on Reddit I found this nice alphabet of 4×3 letters:

It surely Ok to use 4×3 matrices. But does SVD give me good results? Several letters clearly correspond to a rank 2 matrix. Maybe there we can hope for a good approximation with a rank 1 matrix. More than rank 1 will be too tedious for an exercise. Let’s do the letter L. There we have $$A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}$$ as our matrix. A rank 1 approximation seems possible, so let us try. For the SVD $A = U\Sigma V^T$ we find $\left[ 2.175327747161075\mathop{,}1.126032500610494\mathop{,}8.777083671441754 {{10}^{-17}}\right] $ for the non-zero entries of $\Sigma$. For $U$ Maxima gives me $$U = \begin{pmatrix}\mathop{-}0.4082482904638631 & 0.40824829046386296 & \mathop{-}0.3913852529459322 & \mathop{-}0.7165781537579241\\
\mathop{-}0.408248290463863 & 0.408248290463863 & 0.8162675114242799 & 0.019339505161186626\\
\mathop{-}0.4082482904638631 & 0.408248290463863 & \mathop{-}0.42488225847834765 & 0.6972386485967378\\
\mathop{-}0.7071067811865475 & \mathop{-}0.7071067811865475 & 2.154924023251073 {{10}^{-16}} & 5.551115123125783 {{10}^{-17}}\end{pmatrix}$$ and for $V$ Maxima gives me $$V^T = \begin{pmatrix}\mathop{-}0.8880738339771154 & \mathop{-}0.32505758367186804 & \mathop{-}0.32505758367186816\\
0.4597008433809831 & \mathop{-}0.6279630301995542 & \mathop{-}0.6279630301995544\\
0.0 & \mathop{-}0.7071067811865475 & 0.7071067811865475\end{pmatrix}.$$

This is not too bad. Let’s try a rank $1$ approximation with some generous rounding. Take $$u_1^T = [-4, -4, -4, -7]/10$$ and $$v_1^T = [-9, -3,-3]/10$$. The matrix $\Sigma$ suggests that we take something like $2.18 u_1 v_1^T$. But I feel generous and take $3 u_1 v_1^T$. We get $$ 3 u_1 v_1^T = \begin{pmatrix}1.08 & 0.36 & 0.36\\
1.08 & 0.36 & 0.36\\
1.08 & 0.36 & 0.36\\
1.89 & 0.63 & 0.63\end{pmatrix}.$$

One can recognize the L quite well, I think. But we only have two colors, so let us do some rounding to what is closest, 0 or 1: $$\begin{pmatrix}1 & 0 & 0\\
1 & 0 & 0\\
1 & 0 & 0\\
1 & 1 & 1\end{pmatrix}.$$

Perfection!

The reader might complain that the whole example is a bit silly in the sense that we can store the Latin alphabet in 7 bits and a binary 4×3 matrix in 1.5 bytes.