論文の概要: Impossibility Results for Grammar-Compressed Linear Algebra
- arxiv url: http://arxiv.org/abs/2010.14181v1
- Date: Tue, 27 Oct 2020 10:33:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 12:59:32.987558
- Title: Impossibility Results for Grammar-Compressed Linear Algebra
- Title（参考訳）: 文法圧縮線形代数の不可能性
- Authors: Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin K\"unnemann
- Abstract要約: 膨大な量のデータを扱うためには、ベクトルや行列を圧縮することが自然で一般的である。
本稿では, 圧縮されたデータに対して, 元のデータがそんなに小さいかのように, 効率的に計算を実行できるかどうかを問う。
内積、行列ベクトル乗法、行列乗法など、最も基本的な線形代数演算を考える。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 膨大なデータを扱うために、ベクトルや行列を圧縮するのに自然で人気がある。
ベクターをサイズn$からサイズn \ll n$に圧縮すると、保存や送信がより簡単になりますが、処理も簡単になるのでしょうか?
本稿では、ロスレス圧縮スキームについて検討し、圧縮データの計算を元のデータと同じくらい効率的に行うことができるかどうかを問う。
つまり、ある操作が時間複雑性$T(\rm{inputsize})$を持つなら、$T(N)$ではなく、時間$T(n)$で圧縮された表現でそれを実行できますか?
内積、行列ベクトル乗法、行列乗法など、最も基本的な線形代数演算を考える。
特に、2つの圧縮ベクトルが与えられたとき、その内積をo(n)$で計算できるだろうか?
あるいは、最初に圧縮し、次に乗算して、$\Omega(N)$timeを使わなければなりませんか?
答えは圧縮方式に依存する。
Run-Length-Encoding (RLE)のような単純な製品の場合、内部積は$O(n)$ timeで実現できるが、よりリッチなクラスからの圧縮では不可能であることが証明されている。
これは、lempel-zivファミリーのような最も一般的な方法を含む文法圧縮のクラスである。
これらのスキームは単純なRLEよりも圧縮性が高いが、残念なことに、計算の実行ははるかに難しい。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Matrix Compression via Randomized Low Rank and Low Precision
Factorization [47.902465710511485]
現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-17T06:56:57Z) - How to Capture Higher-order Correlations? Generalizing Matrix Softmax
Attention to Kronecker Computation [12.853829771559916]
本稿では,三重相関を捉える注意の一般化について検討する。
この一般化は、変圧器では不可能であった三重結合の検出に関する問題を解くことができる。
構築, アルゴリズム, 下位境界が自然に高次テンソルや相関に一般化されることが示される。
論文 参考訳（メタデータ） (2023-10-06T07:42:39Z) - Fast optimization of common basis for matrix set through Common Singular
Value Decomposition [0.8702432681310399]
CSVD (Common SVD): SVDに基づく高速な一般化手法。
$U$は$sum_i (w_k)q (A_k A_kT)p$と$V$の$sum_k (w_k)q (A_kT A_k)p$で構成されている。
論文 参考訳（メタデータ） (2022-04-18T10:18:51Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳（メタデータ） (2020-09-08T05:39:19Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳（メタデータ） (2020-02-17T21:32:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。