Timezone: »
To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size N down to size n << N, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process?
In this paper we consider lossless compression schemes, and ask if we can run our computations on the compressed data as efficiently as if the original data was that small. That is, if an operation has time complexity T(inputsize), can we perform it on the compressed representation in time T(n) rather than T(N)? We consider the most basic linear algebra operations: inner product, matrixvector multiplication, and matrix multiplication. In particular, given two compressed vectors, can we compute their inner product in time O(n)? Or perhaps we must decompress first and then multiply, spending Omega(N) time?
The answer depends on the compression scheme. While for simple ones such as RunLengthEncoding (RLE) the inner product can be done in O(n) time, we prove that this is impossible for compressions from a richer class: essentially n^2 or even larger runtimes are needed in the worst case (under complexity assumptions). This is the class of \emph{grammarcompressions} containing most popular methods such as the LempelZiv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.
Author Information
Amir Abboud (IBM research)
Arturs Backurs (TTIC)
Karl Bringmann (Saarland University)
Marvin Künnemann (MaxPlanckInstitut für Informatik)
More from the Same Authors

2019 Poster: Subquadratic HighDimensional Hierarchical Clustering »
Amir Abboud · Vincent CohenAddad · Hussein Houdrouge 
2017 Poster: Approximation Algorithms for $\ell_0$Low Rank Approximation »
Karl Bringmann · Pavel Kolev · David Woodruff