論文の概要: Matrix Compression via Randomized Low Rank and Low Precision
Factorization
- arxiv url: http://arxiv.org/abs/2310.11028v1
- Date: Tue, 17 Oct 2023 06:56:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 17:23:34.871249
- Title: Matrix Compression via Randomized Low Rank and Low Precision
Factorization
- Title(参考訳): ランダム化低ランクと低精度因子化による行列圧縮
- Authors: Rajarshi Saha, Varun Srivastava, Mert Pilanci
- Abstract要約: 現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
- 参考スコア(独自算出の注目度): 47.902465710511485
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Matrices are exceptionally useful in various fields of study as they provide
a convenient framework to organize and manipulate data in a structured manner.
However, modern matrices can involve billions of elements, making their storage
and processing quite demanding in terms of computational resources and memory
usage. Although prohibitively large, such matrices are often approximately low
rank. We propose an algorithm that exploits this structure to obtain a low rank
decomposition of any matrix $\mathbf{A}$ as $\mathbf{A} \approx
\mathbf{L}\mathbf{R}$, where $\mathbf{L}$ and $\mathbf{R}$ are the low rank
factors. The total number of elements in $\mathbf{L}$ and $\mathbf{R}$ can be
significantly less than that in $\mathbf{A}$. Furthermore, the entries of
$\mathbf{L}$ and $\mathbf{R}$ are quantized to low precision formats $--$
compressing $\mathbf{A}$ by giving us a low rank and low precision
factorization. Our algorithm first computes an approximate basis of the range
space of $\mathbf{A}$ by randomly sketching its columns, followed by a
quantization of the vectors constituting this basis. It then computes
approximate projections of the columns of $\mathbf{A}$ onto this quantized
basis. We derive upper bounds on the approximation error of our algorithm, and
analyze the impact of target rank and quantization bit-budget. The tradeoff
between compression ratio and approximation accuracy allows for flexibility in
choosing these parameters based on specific application requirements. 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. Our results illustrate that we can achieve
compression ratios as aggressive as one bit per matrix coordinate, all while
surpassing or maintaining the performance of traditional compression
techniques.
- Abstract(参考訳): 行列は、構造化された方法でデータを整理し操作するための便利なフレームワークを提供するため、様々な研究分野で非常に有用である。
しかし、現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源やメモリ使用量の観点から非常に要求される。
極端に大きいが、そのような行列は概して低位であることが多い。
この構造を利用して任意の行列 $\mathbf{a}$ as $\mathbf{a} \approx \mathbf{l}\mathbf{r}$, ここで$\mathbf{l}$ と $\mathbf{r}$ の低階分解を求めるアルゴリズムを提案する。
\mathbf{l}$ と $\mathbf{r}$ の要素の総数は、$\mathbf{a}$ の要素よりもかなり少ない。
さらに、$\mathbf{l}$ と $\mathbf{r}$ のエントリは、低いランクと低い精度の因子化を与えることで$\mathbf{a}$ を圧縮する低精度フォーマットに量子化される。
我々のアルゴリズムはまず列をランダムにスケッチし、次にこの基底を構成するベクトルの量子化によって$\mathbf{A}$の範囲空間の近似基底を計算する。
そして、この量子化された基底に対して$\mathbf{A}$の列の近似射影を計算する。
アルゴリズムの近似誤差の上限を導出し、目標ランクと量子化ビット予算の影響を解析する。
圧縮比と近似精度のトレードオフにより、特定のアプリケーション要件に基づいてこれらのパラメータを選択する柔軟性がある。
画像圧縮,画像およびテキスト埋め込みの最も近い分類,llama-$7$bの圧縮におけるアルゴリズムの有効性を実証的に実証した。
その結果,従来の圧縮技術の性能を上回ったり維持したりしながら,行列座標当たり1ビット程度の攻撃的な圧縮比が得られることが分かった。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。
サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。
本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
論文 参考訳(メタデータ) (2023-11-08T13:29:08Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。
我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
論文 参考訳(メタデータ) (2020-10-01T22:41:41Z) - Approximate Multiplication of Sparse Matrices with Limited Space [27.875251633343666]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。
理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文 参考訳(メタデータ) (2020-09-08T05:39:19Z) - Fast Matrix Square Roots with Applications to Gaussian Processes and
Bayesian Optimization [24.085358075449406]
行列平方根とその逆は機械学習で頻繁に現れる。
我々は,$mathbf K1/2 mathbf b$,$mathbf K-1/2 mathbf b$とその導関数を行列ベクトル乗算(MVM)により計算するための高効率二次時間アルゴリズムを導入する。
提案手法は,Krylov部分空間法と有理近似,典型的には4ドル10分の精度で100ドル未満のMVMを推定する。
論文 参考訳(メタデータ) (2020-06-19T17:56:24Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。