📘

SVD Image Compression

Implement image compression using Truncated Singular Value Decomposition (SVD).

SVD decomposes an image matrix $A$ (m×n) into: $A = U \Sigma V^T$

Where:

$U$ (m×m): Left singular vectors (row patterns)
$\Sigma$ (m×n): Diagonal matrix of singular values
$V^T$ (n×n): Right singular vectors (column patterns)

Truncated SVD keeps only the top $k$ singular values, achieving compression: $A_k = U_k \Sigma_k V_k^T$

The compression ratio is: $\frac{m \times n}{k(m + n + 1)}$

Quality measure: The retained energy/variance is: $\text{energy} = \frac{\sum_{i=1}^{k} \sigma_i^2}{\sum_{i=1}^{r} \sigma_i^2}$

where $r$ is the rank of the original matrix.

Example:

Input:

image = [[100, 100, 100],
         [100, 100, 100],
         [100, 100, 100]]
k = 1

Output:

{'compressed': [[100, 100, 100], [100, 100, 100], [100, 100, 100]], 'compression_ratio': 1.29}

Reasoning:

Step 1: SVD decomposition For a constant image, there's only 1 non-zero singular value. $\sigma_1 = 300$ (sum of all values in the dominant direction)

Step 2: Truncated reconstruction with k=1 Using only the first singular value reconstructs the image exactly (since rank=1).

Step 3: Compression ratio Original: 3×3 = 9 values Compressed storage: k×(m + n + 1) = 1×(3+3+1) = 7 values Ratio = 9/7 ≈ 1.29

The compressed representation stores less data while preserving the image.

Constraints:

image: 2D numpy array (grayscale, values 0-255)
k: Number of singular values to keep
Return: Dictionary with 'compressed' image and 'compression_ratio'
Clip output values to [0, 255] and round to integers

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.