SVD Image Compression

SVD-based image compression represents an image as a matrix and then factorizes it into orthogonal “pattern” matrices and a diagonal matrix of singular values capturing how important each pattern is. Large singular values correspond to dominant structures and smooth variations in the image, while smaller ones capture fine details and noise. Truncating the SVD to the top $k$ singular values gives a low-rank approximation that keeps the most important information while discarding less significant details, yielding a compressed representation.

In this context, compression comes from storing only $U_k \in \mathbb{R}^{m\times k}$, $\Sigma_k \in \mathbb{R}^{k\times k}$, and $V_k^T \in \mathbb{R}^{k\times n}$ instead of the full $m \times n$ matrix. The compression ratio formula $\frac{m n}{k(m + n + 1)}$ compares the number of original pixel values to the number of values needed to store this factorized representation. The energy metric using $\sum$\sigma$_i^2$ reflects how much of the image’s variance (or information) is retained by the top $k$ singular values, and is commonly used to choose $k$ to achieve a desired quality.

---

1. Background Knowledge (key concepts)

• Singular Value Decomposition (SVD) Any real matrix $A \in \mathbb{R}^{m \times n}$ can be decomposed as

$$A = U \Sigma V^T,$$

where:

• $U \in \mathbb{R}^{m\times m}$ and $V \in \mathbb{R}^{n\times n}$ are orthogonal (columns are orthonormal vectors),

• $\Sigma \in \mathbb{R}^{m\times n}$ is diagonal (nonnegative entries $\sigma_1 \ge$\sigma$_2 \ge \dots \ge 0$ on the diagonal),

• $\sigma_i$ are the singular values.

• Low-rank approximation and truncated SVD The rank-$k$ approximation

$$A_k = U_k \Sigma_k V_k^T$$

uses just the first $k$ singular values and corresponding singular vectors (first $k$ columns of $U$ and $V$). This $A_k$ is the best rank-$k$ approximation to $A$ in both Frobenius and spectral norms. In image terms, increasing $k$ improves visual quality but reduces compression.

• Energy / variance interpretation The squared singular values $\sigma_i^2$ correspond to how much “energy” (variance) each component contributes. The energy ratio

$$\text{energy}(k) = \frac{\sum_{i=1}^k \sigma_i^2}{\sum_{i=1}^{r} \sigma_i^2}$$

measures how much of the total information is preserved by the top $k$ components. This lets you trade off compression vs. reconstruction quality.

---

2. Algorithm / Approach

General pattern for SVD image compression:

1. Represent the image as a matrix $A$ (for grayscale), or as separate matrices per channel (R, G, B) for color.
2. Compute SVD of each matrix: $A = U \Sigma V^T$.
3. Choose truncation level $k$ based on:

• user-specified $k$, or
• target energy threshold (e.g., retain 90% energy).

4. Construct truncated SVD: $U_k, \Sigma_k, V_k^T$.
5. Reconstruct compressed image: $A_k = U_k \Sigma_k V_k^T$.
6. Compute metrics:

• compression ratio using $\frac{m n}{k(m + n + 1)}$,
• energy using the formula above.

This is mostly a linear algebra pipeline where the coding challenge is to correctly slice matrices, compute metrics, and manage shapes.

---

3. Step-by-Step Strategy

1. Convert input image to matrix $A$

• If already given as a 2D array, just read its shape: $m, n = A.\text{shape}$.
• For color images, process each channel separately or stack appropriately, depending on task requirements.

2. Compute full SVD Use your language’s linear algebra library, e.g. (Python-style):

U, S, VT = np.linalg.svd(A, full_matrices=True)

• S is a 1D array of singular values $\sigma_i$.
• Build $\Sigma$ or work directly with S and broadcasting.

3. Determine rank $r$ and allowed range of $k$

• The effective rank is $r = \text{number of non-zero (or above a tolerance) singular values}$.
• Constrain $1 \le k \le r$ (often also $\le \min(m, n)$).

4. Construct truncated factors

• $U_k = U[:, :k]$
• $\Sigma_k =$\text{diag}$(S[:k])$ (a $k \times k$ matrix)
• $V_k^T = VT[:k, :]$

Code sketch:

k_singular = S[:k]
Uk = U[:, :k] # (m, k)
VkT = VT[:k, :] # (k, n)
Sigma_k = np.diag(k_singular) # (k, k)

5. Reconstruct the compressed image

A_k = Uk @ Sigma_k @ VkT # (m, n)

6. Compute compression ratio

• Original storage: $m \times n$ numbers.
• Compressed SVD storage: $m k$ (for $U_k$) $+ k$ (for singular values) $+ n k$ (for $V_k^T$) = $k(m + n + 1)$.
• Compression ratio:

compression_ratio = (m * n) / (k * (m + n + 1))

7. Compute energy / retained variance

total_energy = np.sum(S**2) # sum_{i=1}^r sigma_i^2
retained_energy = np.sum(S[:k]**2) # sum_{i=1}^k sigma_i^2
energy_ratio = retained_energy / total_energy

8. (Optional) Choose k by target energy

• Compute cumulative energy:

cumulative = np.cumsum(S**2) / total_energy
k = np.searchsorted(cumulative, target_energy_threshold) + 1

---

4. Common Pitfalls

• Shape mismatches

• Mixing up full_matrices=True/False can change shapes of $U$ and $V^T$.

• Ensure that $U_k$ is $(m, k)$, $\Sigma_k$ is $(k, k)$, $V_k^T$ is $(k, n)$; otherwise matrix multiplication will fail.

• Confusing S vector with $\Sigma$ matrix

• Many libraries return S as a 1D array; you must either construct $\Sigma_k$ or use Uk * S[:k] broadcasting:

A_k = (Uk * S[:k]) @ VkT

• Using $k$ larger than possible

• $k$ cannot exceed $\min(m, n)$ and practically should not exceed the rank $r$. Always clamp or validate $k$.

• Numerical precision issues in rank detection

• Some singular values may be very small but nonzero numerically; if the problem asks for rank $r$, you might need a tolerance, e.g. treat values < $1e{-10}$ as zero.

• Forgetting per-channel processing in color images

• If input is RGB, you need to compress each channel separately or follow the problem’s specified representation; otherwise the image colors will be wrong.

• Incorrect compression ratio calculation

• Do not forget the +1 in $k(m + n + 1)$ (the singular values).

• Make sure you use the original $m,n$, not truncated dimensions.

---

5. Time & Space Complexity

Assuming a single $m \times n$ channel:

• Time complexity
• Full SVD of an $m \times n$ matrix (w.l.o.g.