Impossibility Results for Grammar-Compressed Linear Algebra

• URL: http://arxiv.org/abs/2010.14181v1
• Date: Tue, 27 Oct 2020 10:33:01 GMT
• Title: Impossibility Results for Grammar-Compressed Linear Algebra
• Authors: Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin K\"unnemann
• Abstract summary: To handle vast amounts of data, it is natural and popular to compress vectors and matrices. This paper asks if we can run our computations on the compressed data as efficiently as if the original data was that small. We consider the most basic linear algebra operations: inner product, matrix-vector multiplication, and matrix multiplication.
• Score: 14.85374185122389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \ll 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(\rm{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, matrix-vector 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 Run-Length-Encoding (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 grammar-compressions containing most popular methods such as the Lempel-Ziv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.

Related papers

• Query Efficient Structured Matrix Learning [32.0553563150929]
  We find a near-optimal approximation to $A$ from any finite-sized family of matrices, $mathcalF$.<n>Surprisingly, we show that, in the matvec model, it is possible to obtain a nearly quadratic improvement in complexity, to $tildeO(sqrtlog|mathcalF|)$.<n>As an example, we establish that a near-optimal approximation from any emphlinear matrix family of dimension $q$ can be learned with $tildeO(sqrt
  arXiv  Detail & Related papers  (2025-07-25T14:04:20Z)
• Linearithmic Clean-up for Vector-Symbolic Key-Value Memory with Kroneker Rotation Products [4.502446902578007]
  A computational bottleneck in current Vector-Symbolic Architectures is the clean-up'' step.<n>We present a new codebook representation that supports efficient clean-up.<n>The resulting clean-up time complexity is linearithmic, i.e. $mathcalO(N,textlog,N)$.
  arXiv  Detail & Related papers  (2025-06-18T18:23:28Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Matrix Compression via Randomized Low Rank and Low Precision Factorization [47.902465710511485]
  Modern matrices can involve billions of elements, making their storage and processing quite demanding in terms of computational resources and memory usage. We propose an algorithm that exploits this structure to obtain a low rank decomposition of any matrix $mathbfA$ as $mathbfLmathbfR$. We empirically demonstrate the efficacy of our algorithm in image compression, nearest neighbor classification of image and text embeddings, and compressing the layers of LlaMa-$7$b.
  arXiv  Detail & Related papers  (2023-10-17T06:56:57Z)
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation [12.853829771559916]
  We study a generalization of attention which captures triple-wise correlations. This generalization is able to solve problems about detecting triple-wise connections that were shown to be impossible for transformers. We show that our construction, algorithms, and lower bounds naturally generalize to higher-order tensors and correlations.
  arXiv  Detail & Related papers  (2023-10-06T07:42:39Z)
• Fast optimization of common basis for matrix set through Common Singular Value Decomposition [0.8702432681310399]
  Proposed CSVD (common SVD): fast general approach based on SVD. $U$ as built of eigenvectors of $sum_i (w_k)q (A_k A_kT)p$ and $V$ of $sum_k (w_k)q (A_kT A_k)p$, where $w_k$ are their weights.
  arXiv  Detail & Related papers  (2022-04-18T10:18:51Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  We introduce a new randomized algorithm, Hutch++, which computes a $(1 pm epsilon)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$. We show that it significantly outperforms Hutchinson's method in experiments.
  arXiv  Detail & Related papers  (2020-10-19T16:45:37Z)
• Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
  We develop sparse co-occuring directions, which reduces the time complexity to $widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$ in expectation. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD.
  arXiv  Detail & Related papers  (2020-09-08T05:39:19Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)
• Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits [3.9919781077062497]
  We consider semi-bandits over a set of arms $cal X subset 0,1d$ where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the smallest known regret bound $R(T) = cal OBig( d (ln m)2 (ln T) over Delta_min Big)$, but it has computational complexity $cal O(|cal X|)$ which is typically exponential in $d$, and cannot
  arXiv  Detail & Related papers  (2020-02-17T21:32:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.