論文の概要: Multiplicative updates for symmetric-cone factorizations
- arxiv url: http://arxiv.org/abs/2108.00740v1
- Date: Mon, 2 Aug 2021 09:23:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-03 22:47:26.944445
- Title: Multiplicative updates for symmetric-cone factorizations
- Title（参考訳）: 対称錐分解の乗法的更新
- Authors: Yong Sheng Soh, Antonios Varvitsiotis
- Abstract要約: コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。
SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a matrix $X\in \mathbb{R}^{m\times n}_+$ with non-negative entries, the
cone factorization problem over a cone $\mathcal{K}\subseteq \mathbb{R}^k$
concerns computing $\{ a_1,\ldots, a_{m} \} \subseteq \mathcal{K}$ and $\{
b_1,\ldots, b_{n} \} \subseteq~\mathcal{K}^*$ belonging to its dual so that
$X_{ij} = \langle a_i, b_j \rangle$ for all $i\in [m], j\in [n]$. Cone
factorizations are fundamental to mathematical optimization as they allow us to
express convex bodies as feasible regions of linear conic programs. In this
paper, we introduce and analyze the symmetric-cone multiplicative update (SCMU)
algorithm for computing cone factorizations when $\mathcal{K}$ is symmetric;
i.e., it is self-dual and homogeneous. Symmetric cones are of central interest
in mathematical optimization as they provide a common language for studying
linear optimization over the nonnegative orthant (linear programs), over the
second-order cone (second order cone programs), and over the cone of positive
semidefinite matrices (semidefinite programs). The SCMU algorithm is
multiplicative in the sense that the iterates are updated by applying a
meticulously chosen automorphism of the cone computed using a generalization of
the geometric mean to symmetric cones. Using an extension of Lieb's concavity
theorem and von Neumann's trace inequality to symmetric cones, we show that the
squared loss objective is non-decreasing along the trajectories of the SCMU
algorithm. Specialized to the nonnegative orthant, the SCMU algorithm
corresponds to the seminal algorithm by Lee and Seung for computing Nonnegative
Matrix Factorizations.
- Abstract（参考訳）: 非負の成分を持つ行列 $X\in \mathbb{R}^{m\times n}_+$ が与えられたとき、コーン $\mathcal{K}\subseteq \mathbb{R}^k$ に関するコーン分解問題は、計算 $\{ a_1,\ldots, a_{m} \} \subseteq \mathcal{K}$ と $\{ b_1,\ldots, b_{n} \} \subseteq~\mathcal{K}^*$ が双対に属するので、$X_{ij} = \langle a_i, b_j \rangle$ がすべての $i\in [m], j\in [n] に対して成り立つ。
凸係数分解は、線形円錐プログラムの可能な領域として凸体を表現できる数学的最適化の基礎となる。
本稿では,$\mathcal{K}$が対称であること,すなわち,自己双対で同質である場合,円錐分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。
対称錐は、非負のオルタン(線形計画)、二階の円錐(二階の円錐計画)、正の半定義行列(半定義的計画)の円錐上の線形最適化を研究する共通の言語を提供するため、数学的最適化において中心的な関心を持つ。
SCMUアルゴリズムは、幾何平均の一般化を用いて計算された錐体の巧妙に選択された自己同型を対称錐に適用することにより、反復を更新するという意味で乗法的である。
リーブの凹凸定理とフォン・ノイマンのトレース不等式を対称錐に拡張することにより、平方損失目標がSCMUアルゴリズムの軌道に沿って非減少していることを示す。
非負のオルサントに特化して、SCMUアルゴリズムは非負行列分解を計算するためのLee and Seungによるセミナルアルゴリズムに対応する。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Hierarchies for Semidefinite Optimization in
$\mathcal{C}^\star$-Algebras [0.0]
本稿では,$mathcalCstar$-algebras上での一般コーンプログラムの有限次元緩和法を提案する。
我々は NPA のような一般化された問題に対するよく知られた階層性やラッサール階層、一般 SDP の拡張対称性の低下を示す。
論文 参考訳（メタデータ） (2023-09-25T09:01:30Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳（メタデータ） (2023-05-11T16:07:47Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。
我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。
本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文 参考訳（メタデータ） (2021-12-17T17:04:34Z) - 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) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - A Non-commutative Extension of Lee-Seung's Algorithm for Positive
Semidefinite Factorizations [0.0]
正の半定値分解(PSD)を計算するために,行列乗法更新(MMU)アルゴリズムと呼ぶLee-Seungアルゴリズムの非可換拡張について述べる。
更新方式では,2乗損失目標が非増加的であり,不動点が臨界点に対応することを示す。
論文 参考訳（メタデータ） (2021-06-01T07:55:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。