Image Compression using Singular Value Decomposition (SVD)

Image source: https://www.comet.com/site/blog/image-compression-using-different-machine-learning-techniques/

1.0 The Problem of Image Size

At its core, a digital image is a matrix (a grid) of numbers. The size of this matrix directly correlates to the storage space required. Without compression, images can quickly consume vast amounts of storage and bandwidth.

1.1. Grayscale Images

A grayscale image is the simplest form. It is a 2D grid where each cell (pixel) represents the intensity of light.

Data Structure: A single matrix of size M*N.

Pixel Value: Typically an 8-bit integer (0–255), where 0 is black and 255 is white.

Example: black and white security camera feed

• Imagine a standard Full HD (1920 x 1080) black and white security camera feed.
• Calculation: 19201080 pixels 1 byte/pixel = approx 2.07 MB per image.
• This seems small, but if that camera records video at 30 frames per second, that’s 62 MB per second, or 223 GB per hour. Without compression, storing just one day of footage would require nearly 5.4 Terabytes.

1.2. Color Images

Color images are more complex because they need to represent Red, Green, and Blue (RGB). This effectively triples the data.

Data Structure: Three matrices (channels) of size M*N stacked together. One matrix for Red, one for Green, one for Blue.

Pixel Value: Three 8-bit integers per pixel.

Example: high-resolution photo taken by a modern smartphone

• Consider a high-resolution photo taken by a modern smartphone, say 12 Megapixels (4000 x 3000).
• Calculation: 40003000pixels 3 bytes/pixel = 36,000,000 bytes = 34.3 MB.
• If you take 100 photos on a vacation, that’s 3.4 GB of raw data. If you upload these to a cloud service or social media, it consumes significant data bandwidth and server storage.

1.3 Real-Life Scenario: Why We Need Compression

Let’s look at a practical example: E-commerce Websites (like Amazon or eBay).

The Context: These sites display millions of product images. A single product page might load 5–10 images (thumbnails, main view, zoomed view).

The Challenge:

• User Experience: If every product image was a raw 34 MB file, a user on a mobile 4G connection would wait nearly 30 seconds just to see a picture of a shoe. They would likely leave the site (high bounce rate).
• Cost: The company pays for bandwidth. Serving petabytes of uncompressed images to millions of users daily would cost a fortune in data transfer fees.

The Requirement:

• We need images that look “good enough” to the human eye but are significantly smaller in file size.
• Instead of 34 MB, we need that product photo to be 100 KB — 200 KB (a compression ratio of nearly 300:1).

This is why image compression techniques like SVD (Singular Value Decomposition), JPEG, and PNG are fundamental technologies for the internet. They allow us to discard “less important” visual data to save massive amounts of space and time.

2. Singular Value Decomposition (SVD)

Singular Value Decomposition (SVD) is a powerful mathematical technique that allows us to break down any matrix into three distinct, simpler matrices.

2.1 The Core Concept

Imagine you have a complex recipe. SVD is like identifying the raw ingredients (the “essence”) that make up that dish. You can then recreate the dish using only the most important ingredients, effectively “compressing” the recipe while keeping the main flavor.

2.2 The Mathematical Formula

Any matrix A (representing our image) can be decomposed into:

Where:

• A: The original matrix (e.g., our image).
• U: The “Left Singular Vectors” matrix. Think of these as the “vertical patterns” or columns of the image.
• Σ: The “Singular Values” matrix. This is a diagonal matrix (zeros everywhere except the diagonal). These values represent the strength or energy of each pattern. They are always sorted from largest to smallest.
• V^T: The transpose of the “Right Singular Vectors” matrix. Think of these as the “horizontal patterns” or rows.

2.3 A Simple Example

Let’s take a very small “image” represented by a 2*2 matrix:

When we apply SVD to this matrix A, we get three matrices:

1. Matrix U (Vertical directions):

2. Matrix Σ (Strengths/Energy):

Notice the values 5 and 1. The first value (5) is much larger than the second (1). This tells us the first “layer” of information is 5 times more important than the second.

3. Matrix V^T (Horizontal directions):

3. Compression in Action: “Rank Approximation”

Now, the magic of compression happens. Since the singular values in Σ are sorted by importance, we can choose to keep only the top ones and throw away the small ones.

In our example, let’s keep only the first singular value (the 5) and discard the second one (the 1). This is called a Rank-1 Approximation.

3.1 Original Reconstruction (Perfect Quality)

This is a Perfect match.

3.2 Compressed Reconstruction (Rank-1)

We effectively zero out the second value:

Now, if we multiply the matrices back together:

The Result:

Did we lose information?

Yes. The numbers changed slightly. Did we save space? In this tiny 2 2 example, no. But in a real image with dimensions like 1000 1000, keeping only the top 50 singular values (instead of 1000) allows us to discard massive amounts of data while the reconstructed image (the matrix of numbers) remains visually very close to the original. The “energy” we kept (the 5) captured the bulk of the image’s structure.

4. Python code for SVD

Following is sample code to calculate SVD for gray scale image.

import numpy as np

# 1. Create a 10x10 matrix (our "image")
# A simple gradient pattern where value = row_index + col_index
A = np.zeros((10, 10))
for i in range(10):
    for j in range(10):
        A[i, j] = i + j

print("--- 1. Original Matrix A (10x10) ---")
print(A)
print("\nTotal numbers to store: 100")

# 2. Perform SVD
U, S, Vt = np.linalg.svd(A)

print("\n--- 2. SVD Components ---")
print("Singular Values (Sigma):")
print(np.round(S, 2))
# Note: SVD returns Sigma as a list of values, not a diagonal matrix, for efficiency.

# 3. Rank-1 Approximation (Compression)
# We keep only the first component (k=1)
k = 1

# Extract the top-k components
U_k = U[:, :k]        # First k columns of U (10 x 1)
S_k = np.diag(S[:k])  # First k singular values (1 x 1 diagonal matrix)
Vt_k = Vt[:k, :]      # First k rows of Vt (1 x 10)

# 4. Reconstruct the Compressed Matrix
# Formula: A_approx = U_k * S_k * Vt_k
A_compressed = np.dot(U_k, np.dot(S_k, Vt_k))

print(f"\n--- 3. Compressed Matrix (Rank-{k}) ---")
print(np.round(A_compressed, 1))

# 5. Analyze Savings
original_size = 10 * 10
# Compressed size: k columns of U + k singular values + k rows of Vt
compressed_size = (10 * k) + k + (k * 10) 

print(f"\n--- 4. Storage Comparison (Rank-{k}) ---")
print(f"Original Size:   {original_size} numbers")
print(f"Compressed Size: {compressed_size} numbers (10 from U + 1 from Sigma + 10 from Vt)")
print(f"Compression Ratio: {original_size / compressed_size:.2f}x")
print(f"Space Saved: {100 - (compressed_size/original_size)*100:.1f}%")

# Let's compare a single pixel to check accuracy
# Original A[0,0] was 0. Compressed is typically close but not exact.
print(f"\nCheck Pixel [0,0]: Original = {A[0,0]}, Compressed = {A_compressed[0,0]:.2f}")
print(f"Check Pixel [9,9]: Original = {A[9,9]}, Compressed = {A_compressed[9,9]:.2f}")

Following is output.

--- 1. Original Matrix A (10x10) ---
[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9.]
 [ 1.  2.  3.  4.  5.  6.  7.  8.  9. 10.]
 [ 2.  3.  4.  5.  6.  7.  8.  9. 10. 11.]
 [ 3.  4.  5.  6.  7.  8.  9. 10. 11. 12.]
 [ 4.  5.  6.  7.  8.  9. 10. 11. 12. 13.]
 [ 5.  6.  7.  8.  9. 10. 11. 12. 13. 14.]
 [ 6.  7.  8.  9. 10. 11. 12. 13. 14. 15.]
 [ 7.  8.  9. 10. 11. 12. 13. 14. 15. 16.]
 [ 8.  9. 10. 11. 12. 13. 14. 15. 16. 17.]
 [ 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.]]

Total numbers to store: 100

--- 2. SVD Components ---
Singular Values (Sigma):
[98.39  8.39  0.    0.    0.    0.    0.    0.    0.    0.  ]

--- 3. Compressed Matrix (Rank-1) ---
[[ 2.7  3.2  3.7  4.2  4.7  5.2  5.7  6.2  6.7  7.2]
 [ 3.2  3.8  4.4  5.   5.5  6.1  6.7  7.3  7.9  8.5]
 [ 3.7  4.4  5.   5.7  6.4  7.1  7.8  8.5  9.2  9.9]
 [ 4.2  5.   5.7  6.5  7.3  8.1  8.9  9.6 10.4 11.2]
 [ 4.7  5.5  6.4  7.3  8.2  9.   9.9 10.8 11.7 12.5]
 [ 5.2  6.1  7.1  8.1  9.  10.  11.  11.9 12.9 13.9]
 [ 5.7  6.7  7.8  8.9  9.9 11.  12.  13.1 14.2 15.2]
 [ 6.2  7.3  8.5  9.6 10.8 11.9 13.1 14.3 15.4 16.6]
 [ 6.7  7.9  9.2 10.4 11.7 12.9 14.2 15.4 16.7 17.9]
 [ 7.2  8.5  9.9 11.2 12.5 13.9 15.2 16.6 17.9 19.3]]

--- 4. Storage Comparison (Rank-1) ---
Original Size:   100 numbers
Compressed Size: 21 numbers (10 from U + 1 from Sigma + 10 from Vt)
Compression Ratio: 4.76x
Space Saved: 79.0%

Check Pixel [0,0]: Original = 0.0, Compressed = 2.67
Check Pixel [9,9]: Original = 18.0, Compressed = 19.26
=== Code execution complete ===

5. How do we save space?

The key distinction is between “Storage Representation” (how we save the file to disk) and “Display Representation” (how we show the image on screen).

5.1. What is Stored on Disk (Compressed)

When we save this “compressed image” to a file, we do not save the 100 numbers you see in the output. We only save the “ingredients” needed to build them.

We save exactly these 21 numbers:

• U Column (10 numbers): [-0.21, -0.23, -0.26, ...]
• Sigma (Σ) Value (1 number): [168.4]
• V^T Row (10 numbers): [-0.17, -0.20, -0.23, ...]

Total Stored: 21 floating-point numbers.

Storage Size: If each float is 4 bytes, the file size is 21*4 = 84 bytes.

5.2. What is Displayed on Screen (Reconstructed)

When you want to view the image (e.g., open it in a photo viewer), the computer reads those 21 numbers and performs the multiplication:

The result of that multiplication is the 100-number matrix you see in the output.

The computer must generate these 100 numbers in memory (RAM) to light up the 100 pixels on your screen. But the file on your hard drive remains tiny (21 numbers).

6. Choosing the Optimal Rank (k)

How do we decide exactly which k is the “best”? There is rarely a single correct answer, but data scientists typically use one of two methods to find the optimal balance:

6.1 The “Elbow” Method (Scree Plot)

If you plot the singular values (Σ) on a graph from largest to smallest, you will typically see a sharp drop followed by a long, flat tail. The optimal k is often found at the “elbow” of this curve — the point where the returns diminish, and adding more singular values provides negligible information gain.

6.2 Energy Retention (Cumulative Energy)

A more mathematical approach is to define a threshold of “energy” you want to preserve (e.g., 90% or 95%). The energy is calculated as the sum of the squares of the singular values. You sum the squares of the first k values and divide by the total sum of all squared singular values.

You simply choose the smallest k that satisfies this inequality. For noisy images, you might aim for lower retention (to filter out noise); for medical imaging, you might demand 99% retention.

7. Closing Thoughts on SVD for Image Compression

We’ve walked through the mechanics of Singular Value Decomposition (SVD) using a simple 10*10 matrix. The results were clear: by keeping only the most significant singular values (Rank-1 approximation), we reconstructed a near-perfect image using only roughly 20% of the original data storage.

This simple example highlights several key takeaways about image compression and linear algebra:

7.1. Data isn’t always “dense” with information

Even though an image has 100 pixels (or 12 million), not every pixel carries unique, critical information. Patterns like gradients, solid colors, or repeating textures are mathematically simple. SVD finds this simplicity and allows us to discard the redundancy.

7.2. Compression is a trade-off

In our example, the compression was “lossy.” The reconstructed pixel values (e.g., 17.98 instead of 18.0) were not identical to the original.

High Rank (k): Better quality, less compression.

Low Rank (k): Worse quality (blurrier), higher compression. Finding the “sweet spot” is the art of compression.

7.3. Why SVD isn’t the Standard (JPEG vs. SVD)

In practice, formats like JPEG dominate image compression. They use a technique called the Discrete Cosine Transform (DCT), which is mathematically similar to SVD (both are basis transformations) but has critical advantages:

1. Computational Speed: Calculating SVD for large matrices is computationally expensive (O(N³)). DCT is much faster (O(N log N)), making it feasible for your phone to snap and save photos instantly.
2. Standardization: Storing an SVD-compressed image requires saving three separate matrices (U, Sigma, V^T). JPEG has a standardized way to store coefficients that is universally understood by browsers and OSs.
3. Perceptual Optimization: JPEG quantization tables are specifically tuned to discard information the human eye can’t see (high-frequency color changes). SVD discards based on mathematical variance, which correlates with visual importance but isn’t perfectly tuned to human biology.

7.4 Where is SVD Actually Used?

SVD is far from “just theoretical.” It is a workhorse in other areas of data science and engineering:

• Noise Reduction (Denoising): By keeping the top k values, you often discard “noise” (random static) which tends to live in the smaller singular values. This cleans up data signals.
• Recommender Systems: Netflix and Amazon use SVD-based algorithms to predict what movies or products you’ll like. They decompose the massive “User vs. Movie” matrix to find hidden patterns (latent features) connecting users with similar tastes.
• Dimensionality Reduction (PCA): Principal Component Analysis, a core technique in machine learning for simplifying complex datasets, is fundamentally built on SVD.
• Search Engines (LSI): Latent Semantic Indexing uses SVD to find relationships between words and documents, helping search engines understand that a search for “car” should also match pages about “automobiles.”

So, while you won’t save your holiday photos as .svd files, the algorithm powers the recommendation engines and search tools you use every day. It is a cornerstone of modern data processing.

7.5 Summary

SVD is a powerful lens for viewing data. It teaches us that a complex grid of numbers can often be described by a few simple, dominant vectors. Whether filtering noise from a signal, compressing a photo, or analyzing relationships in a dataset, the core principle remains the same: Keep the signal, discard the noise.

Enjoy learning!!!