MATH347

MATH347 L25: SVD applications

New concepts:
- Solving linear algebra problems through the SVD
- Image compression
- Image decomposition into large-scale, small-scale features

Why does SVD image compression work?

Consider $x_{1}, x_{2} : ℝ \to ℝ$ , data streams in time of inputs $x_{1} (t)$ and outputs $x_{2} (t)$
Is there some function $f$ linking outputs to inputs? $f (x_{1} (t)) = x_{2} (t)$
Seek answer by first asking: is $x_{2}$ correlated to $x_{1}$ ?
Introduce mean values
$μ_{1} ≅ {\overline{x}}_{1} = \frac{1}{N} \sum_{i = 1}^{N} x_{1} (t_{i}) = E [x_{1}], μ_{2} ≅ {\overline{x}}_{2} = \frac{1}{N} \sum_{i = 1}^{N} x_{2} (t_{i}) = E [x_{2}] .$
$E$ is the expectation, a linear mapping, $E : ℝ^{N} \to ℝ$ whose associated matrix is
$𝑬 = \frac{1}{N} [\begin{array}{cccc} 1 & 1 & \dots & 1 \end{array}] .$
Shift data such that ${\overline{x}}_{1} = {\overline{x}}_{2} = 0$ . Define correlation coefficient
$ρ (x_{1}, x_{2}) = \frac{E [x_{1} x_{2}]}{σ_{1} σ_{2}} = \frac{E [x_{1} x_{2}]}{\sqrt{E [x_{1}^{2}] E [x_{2}^{2}]}} = \frac{𝒙_{1}^{T} 𝒙_{2}}{{|| 𝒙_{1} ||}_{} {|| 𝒙_{2} ||}_{}} .$
uncorrelated, if $ρ = 0$ ; correlated, if $ρ = 1$ ; anti-correlated, if $ρ = - 1$ .

Examples

Correlated signals

matlab>>

t=(0:0.01:1)'; x1=t; x2=t.^2; rho=x1'*x2/norm(x1)/norm(x2); disp(rho)

>> 0.9682

Uncorrelated signals

matlab>>

x3=2*(rand(size(x1))-0.5); rho=x1'*x3/norm(x1)/norm(x3); disp(rho)

>> 0.0603

Anticorrelated signals

matlab>>

t=(0:0.01:1)'; x1=t; x2=-t.^2; rho=x1'*x2/norm(x1)/norm(x2); disp(rho)

>> -0.9682

Extend correlation to input, output vectors

Are input and output parameters $𝒙 \in ℝ^{n}$ , $𝒚 \in ℝ^{m}$ well chosen?
Perhaps components are redundant, a more economical description might be
$𝒖 \in ℝ^{q}, 𝒗 \in ℝ^{p}, p < m, q < n$
Extend idea from correlation coefficient: take $N$ measurements
$𝑿 = [\begin{array}{cccc} 𝒙_{1} & 𝒙_{2} & \dots & 𝒙_{n} \end{array}] \in ℝ^{N \times n}, 𝒀 = [\begin{array}{cccc} 𝒚_{1} & 𝒚_{2} & \dots & 𝒚_{n} \end{array}] \in ℝ^{N \times m} .$
Choose origin such that $E [𝒙] = 𝟎, E [𝒚] = 𝟎 .$
Covariance matrix (generalization of single variable variance)
$𝑪_{𝑿} = 𝑿^{T} 𝑿 = [\begin{array}{c} 𝒙_{1}^{T} \\ 𝒙_{2}^{T} \\ ⋮ \\ 𝒙_{n}^{T} \end{array}] [\begin{array}{cccc} 𝒙_{1} & 𝒙_{2} & \dots & 𝒙_{n} \end{array}] = [\begin{array}{cccc} 𝒙_{1}^{T} 𝒙_{1} & 𝒙_{1}^{T} 𝒙_{2} & \dots & 𝒙_{1}^{T} 𝒙_{n} \\ 𝒙_{2}^{T} 𝒙_{1} & 𝒙_{2}^{T} 𝒙_{2} & \dots & 𝒙_{2}^{T} 𝒙_{n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 𝒙_{n}^{T} 𝒙_{1} & 𝒙_{n}^{T} 𝒙_{2} & \dots & 𝒙_{n}^{T} 𝒙_{n} \end{array}]$

Reduced description by truncation of covariance matrix SVD

SVDs: $𝑿 = 𝑼 𝚺 𝑽^{T}$ , $C_{𝑿} = 𝑿^{T} 𝑿 = 𝑽 𝚲 𝑽^{T}$ , $𝚲 = 𝚺^{T} 𝚺$
Take first $q$ column vectors of $𝑽$ , $𝑽_{q} = [\begin{array}{lll} 𝒗_{1} & \dots & 𝒗_{q} \end{array}]$ , $q < n$
$𝒙 = 𝑽_{q} 𝒖 = [\begin{array}{cccc} 𝒗_{1} & 𝒗_{2} & \dots & 𝒗_{q} \end{array}] 𝒖 .$
System description in terms of $𝒖 \in ℝ^{q}$ is more economical than that in terms of $𝒙 \in ℝ^{n}$
In image compression, successive pixel columns are correlated and reduced descriptions are possible