論文の概要: Fast optimization of common basis for matrix set through Common Singular
Value Decomposition
- arxiv url: http://arxiv.org/abs/2204.08242v1
- Date: Mon, 18 Apr 2022 10:18:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-19 15:53:45.262028
- Title: Fast optimization of common basis for matrix set through Common Singular
Value Decomposition
- Title（参考訳）: 共通特異値分解による行列集合の共通基底の高速最適化
- Authors: Jarek Duda
- Abstract要約: 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$で構成されている。
- 参考スコア（独自算出の注目度）: 0.8702432681310399
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: SVD (singular value decomposition) is one of the basic tools of machine
learning, allowing to optimize basis for a given matrix. However, sometimes we
have a set of matrices $\{A_k\}_k$ instead, and would like to optimize a single
common basis for them: find orthogonal matrices $U$, $V$, such that $\{U^T A_k
V\}$ set of matrices is somehow simpler. For example DCT-II is orthonormal
basis of functions commonly used in image/video compression - as discussed
here, this kind of basis can be quickly automatically optimized for a given
dataset. While also discussed gradient descent optimization might be
computationally costly, there is proposed CSVD (common SVD): fast general
approach based on SVD. Specifically, we choose $U$ as built of eigenvectors of
$\sum_i (w_k)^q (A_k A_k^T)^p$ and $V$ of $\sum_k (w_k)^q (A_k^T A_k)^p$, where
$w_k$ are their weights, $p,q>0$ are some chosen powers e.g. 1/2, optionally
with normalization e.g. $A \to A - rc^T$ where $r_i=\sum_j A_{ij}, c_j =\sum_i
A_{ij}$.
- Abstract（参考訳）: SVD(singular value decomposition)は機械学習の基本ツールの一つであり、与えられた行列の基底を最適化することができる。
しかし、代わりに$\{a_k\}_k$という行列の集合があり、それらの単一の共通基底を最適化したい:$u$、$v$という直交行列を見つければ、$\{u^t a_k v\}$ 行列の集合は幾分単純になる。
例えば、DCT-IIはイメージ/ビデオ圧縮で一般的に使用される関数の正規直交基底である。
また、勾配降下最適化は計算コストがかかる可能性があるが、CSVD (Common SVD: fast general approach based SVD) が提案されている。
具体的には、$U$を$\sum_i (w_k)^q (A_k A_k^T)^p$ と $V$ of $\sum_k (w_k)^q (A_k^T A_k)^p$, where $w_k$ are their weights, $p,q>0$ の固有ベクトルの組として選ぶ。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - 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) - Data-Driven Linear Complexity Low-Rank Approximation of General Kernel
Matrices: A Geometric Approach [0.9453554184019107]
K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。
我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
論文 参考訳（メタデータ） (2022-12-24T07:15:00Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
この問題は、スペクトルが$Lambda$と同じ行列で$A$を近似しようとする。
近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
論文 参考訳（メタデータ） (2022-07-06T16:31:44Z) - 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) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
論文 参考訳（メタデータ） (2020-06-15T23:15:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。