論文の概要: Single Pass Entrywise-Transformed Low Rank Approximation
- arxiv url: http://arxiv.org/abs/2107.07889v1
- Date: Fri, 16 Jul 2021 13:22:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-19 18:39:48.288654
- Title: Single Pass Entrywise-Transformed Low Rank Approximation
- Title(参考訳): single pass entrywise-transformed low rank approximation
- Authors: Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff
- Abstract要約: Liang et al.は、$n times n$ matrix $A$ for a $n cdot operatornamepoly(epsilon-1klog n)$ words of memory, with overall error 10|f(A)-[f(A)]_k|_1,22$, where $[f(A)]_k$ is the best rank-$k$ approximation to $f(A)$ and $
- 参考スコア(独自算出の注目度): 44.14819869788393
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In applications such as natural language processing or computer vision, one
is given a large $n \times d$ matrix $A = (a_{i,j})$ and would like to compute
a matrix decomposition, e.g., a low rank approximation, of a function $f(A) =
(f(a_{i,j}))$ applied entrywise to $A$. A very important special case is the
likelihood function $f\left( A \right ) = \log{\left( \left| a_{ij}\right|
+1\right)}$. A natural way to do this would be to simply apply $f$ to each
entry of $A$, and then compute the matrix decomposition, but this requires
storing all of $A$ as well as multiple passes over its entries. Recent work of
Liang et al.\ shows how to find a rank-$k$ factorization to $f(A)$ for an $n
\times n$ matrix $A$ using only $n \cdot \operatorname{poly}(\epsilon^{-1}k\log
n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 +
\operatorname{poly}(\epsilon/k) \|f(A)\|_{1,2}^2$, where $[f(A)]_k$ is the best
rank-$k$ approximation to $f(A)$ and $\|f(A)\|_{1,2}^2$ is the square of the
sum of Euclidean lengths of rows of $f(A)$. Their algorithm uses three passes
over the entries of $A$. The authors pose the open question of obtaining an
algorithm with $n \cdot \operatorname{poly}(\epsilon^{-1}k\log n)$ words of
memory using only a single pass over the entries of $A$. In this paper we
resolve this open question, obtaining the first single-pass algorithm for this
problem and for the same class of functions $f$ studied by Liang et al.
Moreover, our error is $\|f(A)-[f(A)]_k\|_F^2 + \operatorname{poly}(\epsilon/k)
\|f(A)\|_F^2$, where $\|f(A)\|_F^2$ is the sum of squares of Euclidean lengths
of rows of $f(A)$. Thus our error is significantly smaller, as it removes the
factor of $10$ and also $\|f(A)\|_F^2 \leq \|f(A)\|_{1,2}^2$. We also give an
algorithm for regression, pointing out an error in previous work, and
empirically validate our results.
- Abstract(参考訳): 自然言語処理やコンピュータビジョンのようなアプリケーションでは、大きな$n \times d$ matrix $a = (a_{i,j})$ が与えられ、行列分解(例えば、低ランク近似)の関数 $f(a) = (f(a_{i,j}))$ の計算が求められる。
非常に重要な特殊ケースは、可能性関数 $f\left(A \right ) = \log{\left( \left| a_{ij}\right| +1\right)}$ である。
これを行う自然な方法は、単に$a$の各エントリに$f$を適用して、行列の分解を計算することであるが、これは$a$のすべてと複数のエントリへのパスを格納する必要がある。
Liang et al.\ の最近の研究は、$f(A)$ for a $n \times n$ matrix $A$ using only $n \cdot \operatorname{poly}(\epsilon^{-1}k\log n)$ words of memory, with overall error $10\|f(A)-[f(A)]_k\|_F^2 + \operatorname{poly}(\epsilon/k) \|f(A)\|_{1,2}^2$, where $[f(A)]_k$ is the best rank-k$approximation to $f(A)$ and $\|f(A)\|_{1,2}^2$ square of the sum of the row of $f(A)$2$であることを示している。
彼らのアルゴリズムは$a$のエントリを3回パスする。
著者らは、$n \cdot \operatorname{poly}(\epsilon^{-1}k\log n)$$A$のエントリを1回だけパスするだけで、アルゴリズムを得るというオープンな疑問を提起する。
本稿では,この問題に対する最初のシングルパスアルゴリズムと,Liangらによって研究された関数のクラス$f$について,このオープンな問題を解く。
さらに、我々の誤差は $\|f(A)-[f(A)]_k\|_F^2 + \operatorname{poly}(\epsilon/k) \|f(A)\|_F^2$, ここで $\|f(A)\|_F^2$ は$f(A)$の行のユークリッド長の平方の和である。
したがって、この誤差は10$と$\|f(A)\|_F^2 \leq \|f(A)\|_{1,2}^2$の係数を除去するので、かなり小さい。
また、前回の作業でエラーを指摘して回帰のアルゴリズムを与え、その結果を実証的に検証する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳(メタデータ) (2024-10-07T19:47:13Z) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳(メタデータ) (2023-11-13T00:45:41Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank
Approximation [0.0]
カラムサブセット選択をベースとした$ell_p$ローランク近似アルゴリズムで$tildeO(k)$カラムをサンプリングする。
我々は、カラム部分集合選択に基づく$ell_p$低階近似を1p2$で厳密な上限と下限を得るように、結果を拡張した。
論文 参考訳(メタデータ) (2020-07-20T17:50:30Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳(メタデータ) (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。