-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
145 lines (143 loc) · 5.83 KB
/
index.html
File metadata and controls
145 lines (143 loc) · 5.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="stylesheet" href="style.css" />
<link rel="icon" href="Tiger.png" type="image/png" />
<script>
MathJax = {
tex: {
inlineMath: [
['$', '$'],
['\\(', '\\)'],
],
displayMath: [
// start/end delimiter pairs for display math
['$$', '$$'],
['\\[', '\\]'],
],
},
svg: {
fontCache: 'global',
},
};
</script>
<script src="check-for-tex.js" defer></script>
<script
type="text/javascript"
id="MathJax-script"
async
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js"
></script>
<title>SVD</title>
</head>
<body>
<div class="buttons-container">
<a href="/ImageCompression.html" class="button">Image Compression</a>
</div>
<div class="method">
<h2 class="title">Singular Value Decomposition</h2>
<p>
The Singular Value Decomposition (SVD) states that for every matrix $A$ of size $m\times n$ there exist
two sets of vectors, $\{v_1, v_2,\cdots, v_n\}$ orthogonal in $\mathbb{R}^{n},$
$\{u_1, u_2, \cdots, u_m\}$ orthogonal in $\mathbb{R}^m$ and real numbers $\sigma_1\geq\sigma_2\geq\cdots\geq \sigma_r>0$
such that
</p>
<br />
$$Av_i = \sigma_i u_i,\quad \forall i=1, \cdots r,$$
<br>
<p>where $r$ is the rank of the matrix $A$. And </p>
<br />
$$Av_j = 0\quad \forall j=r+1,\cdots, n.$$
<br />
<p>
In matricial notation:
</p>
<br>
$$A
\left[\begin{array}{ccccc}
&&&&\\
&&&&\\
\boldsymbol{v_1} & \hspace{-0.2cm}\cdots &\hspace{-0.2cm}\boldsymbol{v_r} & \hspace{-0.2cm}\cdots & \hspace{-0.2cm}\boldsymbol{v_n}\\
&&&&\\
&&&&
\end{array}\right]=\left[\begin{array}{ccccc}
&&&&\\
&&&&\\
\boldsymbol{u_1} & \hspace{-0.2cm}\cdots &\hspace{-0.2cm}\boldsymbol{u_r} & \hspace{-0.2cm}\cdots & \hspace{-0.2cm}\boldsymbol{u_m}\\
&&&&\\
&&&&
\end{array}\right]\left[\begin{array}{ccc|c}
\sigma_1 & & & \\
& \ddots & & 0\\
& & \sigma_r & \\
\hline
& 0 & & 0
\end{array}\right]$$
<br>
<p>
That is
</p>
<br />
$$AV = U\Sigma$$
<p>As the vectors in the set $\{v_1, v_2,\cdots, v_n\}$ are orthonormal then the matrix $V$ with columns $v_i$ is orthogonal,
that is $VV^{t} = I_n$. Using this and multiplying by $V^T$ on both sides of the expression we get
</p>
$$A = U\Sigma V^T$$
<br>
<p>The SVD of the matrix $A$.</p>
<h3 class="subtitle">Image compression and the Eckart-Young-Mirsky Theorem</h3>
<p>
Given a matrix $A$ of size $m\times n$ and rank $r$, we know that for every $i>r$ $Av_i=0$, so there are
parts in $AV = U\Sigma$ that don't contribute to the multiplication. The important part in the product of those
matrices is in the first $r$ sigma vectors and sigma values, this way we get
</p>
<br>
$$A
\left[\begin{array}{ccc}
&&\\
\boldsymbol{v_1} & \hspace{-0.2cm}\cdots & \hspace{-0.2cm}\boldsymbol{v_r}\\
&&
\end{array}\right]=\left[\begin{array}{ccc}
&&\\
\boldsymbol{u_1} & \hspace{-0.2cm}\cdots & \hspace{-0.2cm}\boldsymbol{u_r}\\
&&
\end{array}\right]\left[\begin{array}{ccc}
\sigma_1 & & \\
& \ddots & \\
& & \sigma_r
\end{array}\right]$$
<br>
<p>And we still have $V_rV_r^T = I_r$ so multiplying on both sides by $V_r^T$ we get to the
<b>reduced SVD decomposition of </b>$\boldsymbol{A}$
</p>
$$A_r = U_r\Sigma_r V_r^T$$
<br>
<p>
The Eckart-Young-Mirsky theorem states that for every unitarily invariant norm $||\cdot||$ then the best $k$-rank
approximation of a matrix $A$ is $A_k$, that is
</p>
$$\min_{r(B)=k}||A-B|| = ||A-A_k||.$$
<br>
<p>This is particularly useful in data science and we shall show how good this approximations are by
compressing an image.
An image is a 2-dimensional array of pixels, each pixel, represented with a square is also an array formed by four numerical
values RGBA, this values represent "how much" Red, Green, Blue and Alpha (alpha is the transparency of the image) there is in
that particular pixel, this values range from $0$ to $255$.
</p>
<p>An image can be converted into greyscale by setting the three values of RGB to the average of them in the original image,
that is setting for each pixel the array $\left[\frac{R+G+B}{3}, \frac{R+G+B}{3},\frac{R+G+B}{3}\right]$, doing so allows us
to transform an image into a big matrix in which every value represents the average of colours in the corresponding pixel.
</p>
<br>
<p>
Using what we've just learned about the SVD, we know due to the Eckart-Young-Mirsky theorem that the image matrix can be very well
aproximated by one of smaller range, making the image lighter. This is what we do in the <a href="/ImageCompression.html" class="link">Image Compression</a>
section.
</p>
</div>
<footer class="footer" target="_blank">Built by <a href="https://github.com/AnadeOre" class="link">Ana Emilia de Orellana</a></footer>
</body>
</html>