SVD Image Compression Tool

An interactive image compression web app built using Singular Value Decomposition (SVD) for low-rank matrix approximation.
This project demonstrates how linear algebra techniques reduce storage while preserving image quality.

---

📌 Features

• Upload any RGB image
• Adjust compression rank using slider
• Real-time compressed image preview
• Channel-wise RGB SVD compression
• Compression ratio calculation
• Reconstruction error (Frobenius norm)
• Rank vs compression analysis graphs
• Download compressed image output

---

🧠 Mathematical Background

Mathematical Foundations (PhD‑Level Exposition)

1. Problem Formulation

Let an image be represented as a matrix
$$ \mathbf{A} \in \mathbb{R}^{m \times n} $$
for a grayscale channel (pixel intensities 0–255). An RGB image has three such matrices $\mathbf{A}_R, \mathbf{A}_G, \mathbf{A}_B$.

Compression seeks a rank‑$k$ matrix $\mathbf{A}_k$ ($k \ll \min(m,n)$) that approximates $\mathbf{A}$ while minimising storage.

---

2. Singular Value Decomposition (SVD)

Theorem. Any real matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ can be factorised as

$$ \boxed{\mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^\top} $$

where

• $\mathbf{U} \in \mathbb{R}^{m \times m}$ is orthogonal: $\mathbf{U}^\top \mathbf{U} = \mathbf{I}_m$
• $\mathbf{V} \in \mathbb{R}^{n \times n}$ is orthogonal: $\mathbf{V}^\top \mathbf{V} = \mathbf{I}_n$
• $\boldsymbol{\Sigma} \in \mathbb{R}^{m \times n}$ is diagonal with singular values

$$ \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0, \qquad r = \mathrm{rank}(\mathbf{A}). $$

Columns of $\mathbf{U}$ and $\mathbf{V}$ are left/right singular vectors.

---

3. Low‑Rank Approximation

Keep only the first $k$ singular values and corresponding vectors:

$$ \mathbf{U}_k = \mathbf{U}(:,1:k) \in \mathbb{R}^{m \times k},\quad \boldsymbol{\Sigma}_k = \mathrm{diag}(\sigma_1,\dots,\sigma_k) \in \mathbb{R}^{k \times k},\quad \mathbf{V}_k^\top = \mathbf{V}(:,1:k)^\top \in \mathbb{R}^{k \times n}. $$

The rank‑$k$ approximation is

$$ \boxed{\mathbf{A}_k = \mathbf{U}_k \boldsymbol{\Sigma}_k \mathbf{V}_k^\top = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^\top}. $$

This is the optimal rank‑$k$ approximation in Frobenius and spectral norms (Eckart–Young–Mirsky).

---

4. Compression Ratio (Storage)

Original storage (one channel): $m n$ numbers.
Compressed storage: $\mathbf{U}_k$ ($mk$), $\boldsymbol{\Sigma}_k$ ($k$), $\mathbf{V}_k^\top$ ($kn$)

$$ S_{\text{comp}} = k(m + n + 1). $$

For RGB (3 channels):

$$ S_{\text{orig}} = 3mn,\qquad S_{\text{comp}} = 3k(m + n + 1). $$

Compression ratio (percentage saved):

$$ \eta = \left(1 - \frac{k(m+n+1)}{mn}\right) \times 100% $$

---

5. Reconstruction Error (Frobenius Norm)

Frobenius norm:

$$ |\mathbf{X}|_F = \sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n} x_{ij}^2}. $$

Error after compression:

$$ \boxed{\varepsilon(k) = |\mathbf{A} - \mathbf{A}_k|_F = \sqrt{\sum_{i=k+1}^{r} \sigma_i^2}}. $$

Relative error:

$$ \varepsilon_{\text{rel}}(k) = \frac{|\mathbf{A} - \mathbf{A}_k|_F}{|\mathbf{A}|_F} \times 100% = \sqrt{\frac{\sum_{i=k+1}^{r} \sigma_i^2}{\sum_{i=1}^{r} \sigma_i^2}} \times 100%. $$

---

6. Energy Retention (Variance Explained)

Total energy = sum of squared singular values:

$$ E_{\text{total}} = \sum_{i=1}^{r} \sigma_i^2. $$

Energy retained by rank‑$k$:

$$ E_{\text{ret}}(k) = \frac{\sum_{i=1}^{k} \sigma_i^2}{\sum_{i=1}^{r} \sigma_i^2} \times 100%. $$

This equals the fraction of variance explained in PCA.

---

7. Optimality (Eckart–Young–Mirsky Theorem)

Theorem. For any $\mathbf{A}$ and any $k < \mathrm{rank}(\mathbf{A})$,

$$ |\mathbf{A} - \mathbf{A}_k|_F = \min_{\mathrm{rank}(\mathbf{B}) \le k} |\mathbf{A} - \mathbf{B}|_F. $$

The truncated SVD $\mathbf{A}_k$ attains the minimum – no other rank‑$k$ matrix yields smaller Frobenius error.

---

8. RGB Image Handling

A colour image is a 3‑tensor $\mathcal{I} \in \mathbb{R}^{m \times n \times 3}$. Decompose into channel matrices:

$$ \mathcal{I} \mapsto {\mathbf{A}_R, \mathbf{A}_G, \mathbf{A}_B},\quad \mathbf{A}_c \in \mathbb{R}^{m \times n}. $$

Compress each channel independently:

$$ \mathbf{A}_c^{(k)} = \mathbf{U}_c^{(k)} \boldsymbol{\Sigma}_c^{(k)} (\mathbf{V}_c^{(k)})^\top,\quad c \in {R,G,B}. $$

Reconstruct by stacking:

$$ \mathcal{I}_{\text{comp}} = \mathrm{stack}(\mathbf{A}_R^{(k)}, \mathbf{A}_G^{(k)}, \mathbf{A}_B^{(k)}). $$

---

9. Computational Complexity

Operation	Complexity
Full dense SVD	$O(\min(m,n)^2 \max(m,n))$
Truncated / randomised SVD (to rank $k$)	$O(k m n)$

For large images, full SVD becomes prohibitive. Scaling requires randomised or iterative methods.

---

10. Numerical Precision

Pixel values are integers in $[0,255]$. To avoid rounding errors:

1. Convert to float64 before SVD.
2. Perform all multiplications in floating point.
3. Clip reconstructed values to $[0,255]$.
4. Convert back to uint8 only for final output.

This ensures the computed Frobenius error matches the theoretical tail‑sum of singular values up to machine epsilon.

---

11. Summary of Key Formulas

Quantity	Formula
SVD	$\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top$
Rank‑$k$ approx	$\mathbf{A}_k = \mathbf{U}_k\boldsymbol{\Sigma}_k\mathbf{V}_k^\top$
Compression ratio	$\eta = \left(1 - \frac{k(m+n+1)}{mn}\right) \times 100%$
Reconstruction error	$\varepsilon(k) = \sqrt{\sum_{i=k+1}^{r} \sigma_i^2}$
Energy retention	$E_{\text{ret}}(k) = \frac{\sum_{i=1}^{k} \sigma_i^2}{\sum_{i=1}^{r} \sigma_i^2} \times 100%$
Optimality	$|\mathbf{A} - \mathbf{A}_k|F = \min{\mathrm{rank}(\mathbf{B})\le k} |\mathbf{A} - \mathbf{B}|_F$
Full SVD complexity	$O(\min(m,n)^2 \max(m,n))$

---

This framework rigorously justifies the implementation and provides exact metrics for the storage–fidelity trade‑off.

📊 Compression Metrics Used

The application computes:

• Compression Ratio (% storage saved)
• Reconstruction Error (Frobenius Norm)

Frobenius norm:

||A − Aₖ||

Lower error indicates better reconstruction quality.

---

🛠 Tech Stack

• Python
• NumPy
• Streamlit
• Pillow
• Matplotlib

---

📂 Project Structure

SVD-Image-Compression-Tool/ │ ├── app.py ├── svd_utils.py ├── requirements.txt ├── sample_images/ └── README.md

---

▶️ How to Run Locally

Clone repository:

git clone https://github.com/BitwiseSage/SVD-Image-Compression-Tool.git

Navigate into folder:

cd SVD-Image-Compression-Tool

Install dependencies:

pip install -r requirements.txt

Run application:

python -m streamlit run app.py

---

📈 Applications of SVD Compression

• Image storage optimization
• Facial recognition preprocessing
• Recommender systems
• Signal processing
• Dimensionality reduction (PCA)

---

📷 Demo

Example compression output:

pdf file of demo placed in sample_images folder as "demo.pdf"

👨‍💻 Authors

Developed as part of a Linear Algebra course project demonstrating practical applications of Singular Value Decomposition (SVD) in image compression and matrix approximation.