The matrix itself is the operation, too, it's a function from R^n to R^m, and that function is what is approximated by matrix compression.

If you are familiar with PCA or SVD, you are already close to understanding a basic form of compression. SVD breaks down an m x n matrix into an nxn rotation matrix, an nxn diagonal scaling matrix, and a n mxn loadings matrix. The ordering of the new matrices is usually with the highest amount of variability described first. So if you take the first, say, 5 of the n dimensions, and only use them, you can reconstruct an approximation of the original matrix that uses approximately 5/n of the original storage.

PCA is often used in machine learning too, and there is such a deep connection between compression that is hard to make explicit or formalize.

The implementation linked here uses Vector Quantization instead:

https://en.wikipedia.org/wiki/Vector_quantization

The furthest I have come was applying an SVD on a 2D Matrix to find the new axes of a skewed ellipsis, but I think I could follow for most of the part. Thanks.

Yeah, that's enough to visualize the idea. If you have a mx2 matrix, and you take each row as a point in 2D space, the compression means projecting all the points along the long dimension of the ellipse. If all the points are along a line, then the matrix is perfectly compressible.

In almost all practical uses of matrix multiplication, we have rounding errors. For example, in 3D it is hard to reverse exactly a rotation and get the exact initial position back.

I don't know what amount of losses we are talking about but in deep learning, several operations don't require a crazy level of compression, and it led to some lightweight float implementations (bfloat, on 16 bits, being the most common but there are also 8 bits floats for extreme cases)

If that's really a 10-100x speed increase at the cost of a bit of loss, I am sure machine learning will love it.

Neural networks generally tolerate lossy compression. So they are OK here provided that they have demonstrated that their compressed op networks still manage to reach comparable accuracy.

Unfortunately, AFAIKT, the experiments are not very comprehensive. So I wouldn't be surprised to find a good lossy compression for this use case, but I'm not sure if this is such.