3 ms·

THis sounds and looks impressive, but this part struck me: "If you ... and can tolerate lossy compression" What does this mean? I wouldn't have thought that m

by jansan 4y ago

THis sounds and looks impressive, but this part struck me: "If you ... and can tolerate lossy compression" What does this mean? I wouldn't have thought that matrix operations can be lossy. Does anybody know to what extend they are lossy and where this would be acceptable?

Iv 4y ago
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.
- deleted 4y ago
  [deleted]
epistasis 4y ago
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 https://en.wikipedia.org/wiki/Vector_quantization
- jansan 4y ago
  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.
  - epistasis 4y ago
    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.
amitport 4y ago
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.

by jansan 4y ago

Iv 4y ago

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.

deleted 4y ago
[deleted]

epistasis 4y ago

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 https://en.wikipedia.org/wiki/Vector_quantization

jansan 4y ago
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.
- epistasis 4y ago
  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.

amitport 4y ago

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.