Breaking a Matrix Apart

• Call my matrix \(\mathbf{A} \in \mathbb{R}^{m \times n}\)

• We can decompose this matrix into the product of three matrices \[ \mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^\top \]

• \(\mathbf{U}\) are the “row-shapes” that show how each component spreads down the image (vertical patterns)

• \(\boldsymbol{\Sigma}\) is a diagonal matrix that ranks the “importance” of components - bigger values means more important; small ones can be dropped

• \(\mathbf{V}\) are the “column-shapes” that show how each component spreads across the image (horizontal patterns).

Basic Properties

• The SVD exists for all real matrices (square or rectangular)
• The pieces have a fixed role:
  • \(\mathbf{U}\) and \(\mathbf{V}\) are orthonormal matrices (\(\mathbf{U}^\top \mathbf{U} = \mathbf{I}_m\) and \(\mathbf{V}^\top \mathbf{V} = \mathbf{I}_n\))
  • \(\boldsymbol{\Sigma}\) is a (ordered) diagonal with non-negative numbers (singular values)

Singular values are ordered from greatest to least – they measure the importance of the patterns in the data or image.

Eckart-Young-Mirsky Theorem

where \[ \| \mathbf{X} \|_2 = \boldsymbol{\sigma}_{\text{max}} \quad \text{and} \quad \| \mathbf{X} \|_F = \sqrt{\sum_{i, j}^{mn} x_{i,j}}. \]

Eckart-Young-Mirsky Theorem

• Singular values measure how much each rank-one component contributes.
• Keep the biggest \(k\) components and you lose exactly the next singular value in spectral norm and the squared sum of the remaining singular values in Frobenius norm, \[ \| \mathbf{A} - \mathbf{A}_k \|_2 = \boldsymbol{\sigma}_{k+1}, \quad \| \mathbf{A} - \mathbf{A}_k \|_F = \left(\sum_{i=k+1}^{\min(m, n)} \boldsymbol{\sigma}_i\right). \]

Application to Compression

• This image can be represented by a matrix \(\mathbf{A} \in \mathbb{R}^{921 \times 1620}\).
• The SVD gives us \(\mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^\top\) where
  • \(\mathbf{U} \in \mathbb{R}^{921 \times 921}\)
  • \(\boldsymbol{\Sigma} \in \mathbb{R}^{921 \times 1620}\)
  • \(\mathbf{V} \in \mathbb{R}^{1620 \times 1620}\)

Singular Values in a Rectangular Matrix

• \(\boldsymbol{\Sigma}\) is rectangular, so we have \(\min(921, 1620) = 921\) singular values.
• What happens if we simply take the largest \(k = 920\) singular values? In other words, we only “compress” the image by removing the last singular value and vector?
• This is a reduction in the rank of the original image by one, we should expect minimal noise reduction.

k = 921

k = 920

k = 919

k = 918

k = 500

k = 100

k = 50

k = 25

k = 2

But how does this compress?

• Instead of storing \(m \times n\) numbers, we store \(m \times k + n \times k + k\) numbers
• In our example, we have \(921 \times 1620 = 1492020\) numbers to store.
• If we were to use \(k = 100\), we store \(921 \times 100 + 1620 \times 100 + 100 = 254200\) numbers
• This is approximately \(17\)% the size of the original image!
• But how do we determine the optimal number of \(k\) in practice?

Selecting k

• We may use a scree plot, which shows us how much information we lose at each \(k\).

Cumulative Energy / Variance Explained

• Alternatively, we may have a Cumulative Energy based estimator to estimate the number \(k\) in practice

• Allows us to obtain a specific value \(k\) without relying on our judgement \[ k^* = \min \left( k: \frac{\sum_{i=1}^k \boldsymbol{\sigma}_i^2}{\sum_{i=1}^{\min(m, n)} \boldsymbol{\sigma}_i^2} \geq \tau\right) \]

• Keep enough singular values to capture a fixed fraction of total variance or “energy”

Cumulative Energy / Variance Explained

S = svd_porco.S
τ = 0.999
cumulative_energy = cumsum(S.^2) ./ sum(S.^2)
k_star = findfirst(x -> x >= τ, cumulative_energy)

68

• In keeping \(99.9\)% of the variance, I want to have \(k = 68\).
• This reduced the image storage from \(1492020\) numbers to store to \(172856\) numbers to store.
• The new image is approximately \(11\)% the size of the original image

Image with k = 68

Conclusion

• SVD expresses an image as orthonormal matrices weighted by singular values – most visual information is concentrated in the first few components

• Eckart-Young-Mirsky guarantees the truncated SVD is the optimal rank-\(k\) approximation (error controlled exactly by the discarded singular values in spectral/Frobenius norms).

• Practical rule: pick \(k\) from a scree or cumulative-energy cutoff; e.g., \(99.9\)% energy at \(k=68\) reduced storage to \(\approx 11\)% with minimal visual loss.