Brief
A grayscale photo is a matrix of brightness values. This project compresses it by writing that matrix as a sum of simple layers and keeping only the most important ones. Then you put a slider on it and watch the photo sharpen as you add layers.
The tool is the singular value decomposition. Any matrix can be written as
Each term is an outer product: a column times a row, one layer with the same shape as the photo. The singular values say how much each layer matters. Keep the first and you have a rank- approximation. It stores numbers instead of , and no other rank- matrix is closer to the original.
You compute it with tools you already have. The right singular vectors are the eigenvectors of , and its eigenvalues are . So the power iteration from BM-07 finds , and follows.
DATA · your photos
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- Your top 50 singular values match numpy.linalg.svd within 1e-4, recorded with `python tools/mlarena.py record BM-08 "<largest difference>"`.
- A table with your PSNR and JPEG's PSNR at 10% size for at least three photos, and one sentence on which wins and why.
- The slider redraws in well under a second at 512 pixels wide, because nothing is recomputed except the sum of k layers.
Side quests
Terms in plain words
- Singular value decomposition (SVD)
- Any matrix can be written as A = UΣVᵀ, where U and V have perpendicular unit columns and Σ is diagonal with non-negative entries in decreasing order.
- Singular value
- One diagonal entry of Σ. It says how much that layer of the image contributes; most photos have a few big ones and a long tail of small ones.
- Low-rank approximation
- Keep only the first k layers of the SVD. By the Eckart-Young theorem, no other rank-k matrix is closer to A.
- Rank
- The number of independent rows (or columns) in a matrix. A rank-k image is a sum of k outer products.
- Deflation
- After finding the top eigenvector, remove its part from the matrix so power iteration finds the next one.