ML Katas

Singular Value Decomposition (SVD) is a powerful matrix factorization technique with numerous applications, including dimensionality reduction, noise reduction, and data compression. Any real $m\times n$ matrix $A$ can be decomposed into $A=U\Sigma V^T$, where $U$ is an $m\times m$ orthogonal matrix, $\Sigma$ is an $m\times n$ diagonal matrix containing singular values, and $V^T$ is an $n\times n$ orthogonal matrix.

By keeping only the top $k$ largest singular values and their corresponding singular vectors, we can obtain a low-rank approximation of the original matrix $A_k=U_k{\Sigma }_k{V}_k^T$. This approximation can be used for compression.

Your task is to implement a function that performs SVD-based image compression.

Implementation Details: 1. Load Image: Load a grayscale image (e.g., using PIL or matplotlib.image). Convert it to a NumPy array. 2. SVD: Apply np.linalg.svd to the image matrix to obtain $U$, $\Sigma$ (as a 1D array of singular values), and $V^T$. 3. Truncation: For a given number of components k, reconstruct the image using only the first k singular values and vectors: $U[:,:k]@np.diag(\Sigma [:k])@V_T[:k,:]$. 4. Compression Ratio: Calculate the compression ratio (original size / compressed size) and the percentage of variance explained by the chosen k components. * The original image has $m\times n$ elements. * The compressed image (using $k$ components) requires storing $U_k$ ($m\times k$), ${\Sigma }_k$ ($k\times k$ or just $k$ values), and $V_k^T$ ($k\times n$). The number of elements to store is approximately $k(m+n+1)$.

Implement a function compress_image_svd(image_path, k_components) that: * Loads the image. * Performs SVD. * Reconstructs the image with k_components. * Returns the original image, compressed image, and the compression ratio.

Verification: 1. Choose a sample grayscale image (you can find one online or create a simple one programmatically). 2. Test your function with different values of k (e.g., 10, 50, 100). 3. Display the original and compressed images side-by-side using matplotlib.pyplot.imshow. Observe how the image quality changes with k. 4. Verify that your compression ratio calculation is correct. 5. (Optional, advanced) Compare the reconstruction error (e.g., Frobenius norm of the difference between original and reconstructed) for different k values.