論文の概要: When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
- arxiv url: http://arxiv.org/abs/2407.03250v4
- Date: Tue, 15 Apr 2025 09:00:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-16 22:05:45.740345
- Title: When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
- Title（参考訳）: ビッグデータが実際に低ランクである場合、あるいは特定の関数生成行列のエントリワイズ近似
- Authors: Stanislav Budzinskiy,
- Abstract要約: この記事は、2$m$次元変数の滑らかな関数をサンプリングすることによって生成される行列の低ランク近似に関するものである。
特定の解析関数のクラスに対して、そのような$n times n$行列は、$m$とは独立で$log(n)$として成長するランクの正確なエントリーワイド近似を認めるという主張を取り巻くいくつかの誤解を特定する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The article concerns low-rank approximation of matrices generated by sampling a smooth function of two $m$-dimensional variables. We identify several misconceptions surrounding a claim that, for a specific class of analytic functions, such $n \times n$ matrices admit accurate entrywise approximation of rank that is independent of $m$ and grows as $\log(n)$ -- colloquially known as ''big-data matrices are approximately low-rank''. We provide a theoretical explanation of the numerical results presented in support of this claim, describing three narrower classes of functions for which function-generated matrices can be approximated within an entrywise error of order $\varepsilon$ with rank $\mathcal{O}(\log(n) \varepsilon^{-2} \log(\varepsilon^{-1}))$ that is independent of the dimension $m$: (i) functions of the inner product of the two variables, (ii) functions of the Euclidean distance between the variables, and (iii) shift-invariant positive-definite kernels. We extend our argument to tensor-train approximation of tensors generated with functions of the ''higher-order inner product'' of their multiple variables. We discuss our results in the context of low-rank approximation of (a) growing datasets and (b) attention in transformer neural networks.
- Abstract（参考訳）: この記事は、2$m$次元変数の滑らかな関数をサンプリングすることによって生成される行列の低ランク近似に関するものである。
特定の解析関数のクラスに対して、例えば$n \times n$行列は、$m$とは独立で$\log(n)$として成長するランクの正確なエントリーワイド近似を許容する。
この主張を支持するために提示された数値的な結果について理論的に説明し、関数生成行列が次数$\varepsilon$のエントリーワイド誤差で近似できる関数の3つのより狭いクラスを記述し、階数$\mathcal{O}(\log(n) \varepsilon^{-2} \log(\varepsilon^{-1})$は次元$m$とは独立である。
i) 2つの変数の内積の関数
(ii)変数とユークリッド距離の関数
(iii)シフト不変正定核。
我々は、これらの変数の'高階内積'の関数で生成されるテンソルのテンソル-トレイン近似に我々の議論を拡張した。
低ランク近似の文脈における我々の結果について議論する。
(a)成長するデータセット
b) 変圧器ニューラルネットにおける注意
関連論文リスト
- An approximation of the $S$ matrix for solving the Marchenko equation [0.0]
ここでは、有理関数の和として定式化された運動量$q$に対する$S$-行列依存の新たな近似と、truncated Sinc 級数を示す。
このアプローチにより、特定の解像度で$S$行列をポイントワイズで決定することができ、共鳴挙動などの重要な特徴を高精度に捉えることができる。
論文 参考訳（メタデータ） (2024-10-27T11:06:28Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳（メタデータ） (2022-05-12T18:50:21Z) - Perturbation Analysis of Randomized SVD and its Applications to
High-dimensional Statistics [8.90202564665576]
一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。
3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Computationally Efficient Approximations for Matrix-based Renyi's
Entropy [33.72108955447222]
最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。
そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。
我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
論文 参考訳（メタデータ） (2021-12-27T14:59:52Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。
最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
論文 参考訳（メタデータ） (2021-02-15T13:24:41Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。