6.3. Singular Value Decomposition

We introduce now a tool to investigate the last condition in this finite-dimensional setting: the singular value decomposition of matrices.

Lemma 6.4 (SVD)

Any matrix \(A \in \mathbb{R}^{k \times n}\) can be written in the form

\[A = U D V^T\]

with \(U \in \mathbb{R}^{k \times k}\) and \(V \in \mathbb{R}^{n \times n}\) orthogonal matrices, i.e.

\[U^T U = U U^T = I \quad \text{and} \quad V^T V = V V^T = I,\]

and \(D \in \mathbb{R}^{k \times k}\) is a diagonal matrix where the diagonal elements \(d_{ii}\) are the singular values \(\sigma_i\), which are positive and sorted in decreasing order:

\[\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(k,n)} \geq 0.\]

For the case \(k = n\) we only worry about continuity and we can write

\[A^{-1} = (UDV^T)^{-1} = (V^T)^{-1} D^{-1} U^{-1} = V D^{-1} U^T,\]

with \(D^{-1} = \operatorname{diag}\!\left(\tfrac{1}{\sigma_1}, \ldots, \tfrac{1}{\sigma_k}\right)\).

Now we can see that

\[\|A^{-1}\| = \|V D^{-1} U^T\| \leq \|V\|\,\|D^{-1}\|\,\|U^T\| = \|D^{-1}\|,\]

with

\[\|D^{-1}\| = \|D^{-1}\|_2 = \sqrt{\lambda_{\max}(D^{-T}D^{-1})} = \frac{1}{\sigma_k}.\]

We observe by increasing \(k \in \mathbb{N}\), the error \(A^{-1}\varepsilon\) gets stronger amplified.

We will now introduce different regularisation concepts.

6.3.1. Truncated Singular Value Decomposition (TSVD)

Let \(\varepsilon > 0\) be a threshold for the smallest singular value of \(A\) and let

\[r \coloneqq \max_{j \geq 0}\{\sigma_j \geq \varepsilon\}\]

be the index of the smallest singular value above the threshold. Then we construct a matrix

\[S_\varepsilon = \begin{pmatrix} \frac{1}{\sigma_1} & & 0 \\ & \ddots & \\ & & \frac{1}{\sigma_r} \\ 0 & & & \ddots \\ & & & & 0 \end{pmatrix}\]

such that we get a regularised reconstruction by:

\[u = A_\varepsilon^{-1} f = V S_\varepsilon U^T f.\]

1. The operator \(A_\varepsilon^{-1} \colon \mathbb{R}^k \to \mathbb{R}^n\) is a well-defined linear map with the property:

   \[\|A_\varepsilon^{-1}\| = \|VS_\varepsilon U^T\| \leq \|V\|\,\|S_\varepsilon\|\,\|U^T\| = \|S_\varepsilon\| = \frac{1}{\sigma_r} \leq \frac{1}{\varepsilon}.\]

   \(\Rightarrow\) Continuity of the TSVD regularised inversion.

2. The bigger we choose \(\varepsilon\), the less our noise gets amplified.

3. On the other hand, the more singular values we drop, the less information we retain.