Crazy how much you can compress the Mondrian with this method with almost no loss
Image Compression with Singular Value Decomposition
31–40 of 47 posts
Re: Image Compression with Singular Value Decomposition
#32SVD is probably the most important theorem in linear algebra. Basically you can take any matrix and find how much it rotates and stretches as a linear transformation
[deleted]
Re: Image Compression with Singular Value Decomposition
#33SVD is probably the most important theorem in linear algebra. Basically you can take any matrix and find how much it rotates and stretches as a linear transformation
It is a tough battle between SVD and the concept of eigenvalues/vectors. SVD is only meaningful for linear operators between inner product spaces, whereas eigenvalues/vectors do not even require a norm. On the other hand, eigenvectors are only meaningful for linear operators from a space to itself.
Re: Image Compression with Singular Value Decomposition
#34Funny enough, I did this same project (minus the fancy web interface) for a numerical linear algebra course in college—except I had to do it in Matlab. It's worse than just about any "real" image compression algorithm, but it works! (Plus you get lossless compression if your image is low-rank.)
It is interesting that lossy compression algorithms are better, despite the Eckart–Young–Mirsky theorem. I guess “best low rank approximation under unitarily invariant norms“ doesn’t mean much to eyeballs though.
Images have structure that can be exploited, and exploitable structure is everything. A Fibonacci spiral isn't going to have a nice low rank decomposition but it can be specified exactly (and thus reproduced exactly) in a small handful of bytes. EYM is a structure-free guarantee, so we can't expect it to show that SVD would perform better on the natural image manifold than would purpose-built algorithms.
Re: Image Compression with Singular Value Decomposition
#35One issue with SVD is its significant time complexity compared to, for example, the Discrete Cosine Transform used in JPEG
SVD is used more for mathematical elegance than practicality (like ordinary least squares) In data science most traditional usecases for SVD are superceded by other algorithms (UMAP is especially popular these days).
Can you build image compression on UMAP?
Re: Image Compression with Singular Value Decomposition
#36It's funny how the higher compression ratios make everything look similar to a style Gerhard Richter often used. It could be used as an effect in painting apps.
Re: Image Compression with Singular Value Decomposition
#37Funny enough, I did this same project (minus the fancy web interface) for a numerical linear algebra course in college—except I had to do it in Matlab. It's worse than just about any "real" image compression algorithm, but it works! (Plus you get lossless compression if your image is low-rank.)
It is interesting that lossy compression algorithms are better, despite the Eckart–Young–Mirsky theorem. I guess “best low rank approximation under unitarily invariant norms“ doesn’t mean much to eyeballs though.
Perceptual loss is different from mathematical RMSe loss. There has been a lot of work into making things that decompress into something mathematically completely different, but which to Mk1 Human Eyeball looks very similar.
Re: Image Compression with Singular Value Decomposition
#38SVD is probably the most important theorem in linear algebra. Basically you can take any matrix and find how much it rotates and stretches as a linear transformation
It is a tough battle between SVD and the concept of eigenvalues/vectors. SVD is only meaningful for linear operators between inner product spaces, whereas eigenvalues/vectors do not even require a norm. On the other hand, eigenvectors are only meaningful for linear operators from a space to itself.
SVD is just an extension of the Eigenvector Decomposition to allow the two orthogonal matrices to not be equal. Think of SVD as Eigenvectors of your data both in a rowwise and colwise perspective and intuitively it works out pretty well.
Re: Image Compression with Singular Value Decomposition
#39One issue with SVD is its significant time complexity compared to, for example, the Discrete Cosine Transform used in JPEG
SVD is used more for mathematical elegance than practicality (like ordinary least squares) In data science most traditional usecases for SVD are superceded by other algorithms (UMAP is especially popular these days).
There are loads of numerical algorithms where the SVD is the tool of choice because of its particular optimality properties.
Re: Image Compression with Singular Value Decomposition
#40Basically this expresses the image as an image where each row is a linear combination of a set of K rows, with different coefficients for each row (or equivalently for columns).
In general it doesn't make sense to compress images this way, since the algorithm is not invariant with respect to 2D image rotation, a very relevant operation for realistic images, but is invariant with respect to row/column permutations, which are not a relevant operation for realistic images.