論文の概要: A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations

• arxiv url: http://arxiv.org/abs/2106.00293v1
• Date: Tue, 1 Jun 2021 07:55:09 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-02 23:12:40.487062
• Title: A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations
• Title（参考訳）: 正半定因子化のためのリー・ソンのアルゴリズムの非可換拡張
• Authors: Yong Sheng Soh, Antonios Varvitsiotis
• Abstract要約: 正の半定値分解(PSD)を計算するために,行列乗法更新(MMU)アルゴリズムと呼ぶLee-Seungアルゴリズムの非可換拡張について述べる。 更新方式では,2乗損失目標が非増加的であり,不動点が臨界点に対応することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a matrix $X\in \mathbb{R}_+^{m\times n}$ with nonnegative entries, a Positive Semidefinite (PSD) factorization of $X$ is a collection of $r \times r$-dimensional PSD matrices $\{A_i\}$ and $\{B_j\}$ satisfying $X_{ij}= \mathrm{tr}(A_i B_j)$ for all $\ i\in [m],\ j\in [n]$. PSD factorizations are fundamentally linked to understanding the expressiveness of semidefinite programs as well as the power and limitations of quantum resources in information theory. The PSD factorization task generalizes the Non-negative Matrix Factorization (NMF) problem where we seek a collection of $r$-dimensional nonnegative vectors $\{a_i\}$ and $\{b_j\}$ satisfying $X_{ij}= a_i^\top b_j$, for all $i\in [m],\ j\in [n]$ -- one can recover the latter problem by choosing matrices in the PSD factorization to be diagonal. The most widely used algorithm for computing NMFs of a matrix is the Multiplicative Update algorithm developed by Lee and Seung, in which nonnegativity of the updates is preserved by scaling with positive diagonal matrices. In this paper, we describe a non-commutative extension of Lee-Seung's algorithm, which we call the Matrix Multiplicative Update (MMU) algorithm, for computing PSD factorizations. The MMU algorithm ensures that updates remain PSD by congruence scaling with the matrix geometric mean of appropriate PSD matrices, and it retains the simplicity of implementation that Lee-Seung's algorithm enjoys. Building on the Majorization-Minimization framework, we show that under our update scheme the squared loss objective is non-increasing and fixed points correspond to critical points. The analysis relies on Lieb's Concavity Theorem. Beyond PSD factorizations, we use the MMU algorithm as a primitive to calculate block-diagonal PSD factorizations and tensor PSD factorizations. We demonstrate the utility of our method with experiments on real and synthetic data.
• Abstract（参考訳）: 非負の成分を持つ行列 $X\in \mathbb{R}_+^{m\times n}$ が与えられたとき、$X$ の正半定値 (PSD) 分解は$r \times r$-dimensional PSD 行列 $\{A_i\}$ と $\{B_j\}$ の集合であり、すべての$\i\in [m],\ j\in [n]$ に対して$X_{ij}= \mathrm{tr}(A_i B_j)$ を満たす。 psd因子分解は、情報理論における量子資源の力と限界だけでなく、半定値プログラムの表現力の理解と基本的に結びついている。 psd因子分解タスクは、非負行列因子分解(nmf)問題を一般化し、r$-次元非負ベクトルの集まりである$\{a_i\}$と$\{b_j\}$を満たす$x_{ij}= a_i^\top b_j$, for all $i\in [m],\j\in [n]$ -- ここで、psd因子分解の行列を対角化として選択することで後者の問題を回復することができる。 行列のNMFを計算するための最も広く使われているアルゴリズムは、Lee and Seungによって開発された乗算更新アルゴリズムであり、更新の非負性は正の対角行列でスケーリングすることで保存される。 本稿では,PSD分解の計算のために,行列乗法更新(MMU)アルゴリズムと呼ぶLee-Seungアルゴリズムの非可換拡張について述べる。 MMUアルゴリズムは、適切なPSD行列の行列幾何学平均と一致スケーリングによって更新がPSDのままであることを保証する。 また,Majorization-Minimizationフレームワークに基づいて,2乗損失目標が非増加的であり,固定点が臨界点に対応することを示す。 この分析はリーブのConcavity Theoremに依存する。 PSD分解以外にも、MMUアルゴリズムをプリミティブとしてブロック対角PSD分解とテンソルPSD分解を計算する。 実データと合成データの実験により,本手法の有用性を実証する。

関連論文リスト

• Majorization-minimization for Sparse Nonnegative Matrix Factorization with the $\beta$-divergence [2.3787352248749376]
  他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。 標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。 我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-07-13T16:09:29Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。 SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
  論文  参考訳（メタデータ） (2021-08-02T09:23:39Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles [12.005731086591139]
  Householder Dice (HD) は、高密度ランダム行列アンサンブルのダイナミクスを翻訳不変特性でシミュレートするアルゴリズムである。 HDアルゴリズムのメモリとコストはそれぞれ$mathcalO(nT)$と$mathcalO(nT2)$である。 数値結果は、高次元ランダムシステムの研究における新しい計算ツールとしてのHDアルゴリズムの約束を示しています。
  論文  参考訳（メタデータ） (2021-01-19T04:50:53Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  位相探索(PR)とアフィンランク最小化(ARM)アルゴリズムに基づいてPSDMFアルゴリズムを設計可能であることを示す。 このアイデアに触発され、反復的ハードしきい値(IHT)に基づくPSDMFアルゴリズムの新たなファミリーを導入する。
  論文  参考訳（メタデータ） (2020-07-24T06:10:19Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。