論文の概要: Manifold-based Algorithms for the Hadamard Decomposition
- arxiv url: http://arxiv.org/abs/2605.28980v1
- Date: Wed, 27 May 2026 18:35:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-30 02:45:55.231367
- Title: Manifold-based Algorithms for the Hadamard Decomposition
- Title（参考訳）: アダマール分解のためのマニフォールドアルゴリズム
- Abstract要約: アダマール分解は標準的な低ランク近似よりも表現力が高い。
我々はアダマール分解を計算するための3つの新しいアルゴリズムを開発した。
新しいアルゴリズムは、合成データと実データの両方で効率的で競争力がある。
- 参考スコア（独自算出の注目度）: 9.842769671181276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a matrix $X$, and two ranks $r_1$ and $r_2$, the Hadamard decomposition (HD) looks for two low-rank matrices, $X_1$ of rank $r_1$ and $X_2$ of rank $r_2$, both of the same size as $X$, such that $X\approx X_1\circ X_2$, where $\circ$ is the Hadamard (element-wise) product. In most cases, HD is more expressive than standard low-rank approximations such as the truncated singular value decomposition (TSVD), as it can represent higher-rank matrices with the same number of parameters; this is because the rank of $X_1 \circ X_2$ is generically equal to $r_1 r_2$. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation $X\approx WH^\top$ where $W$ and $H$ have $r_1 r_2$ columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation $X\approx X_1\circ X_2$ and relies on the Manopt toolbox. The other two rely on the reformulation $X\approx WH^\top$: one is a block projected gradient method, and the other is a manifold-based gradient descent algorithm that does not require projection onto the feasible set. The last two algorithms are particularly effective for handling large sparse data. We also propose new initializations that allow us to improve the accuracy of the HD. We compare our algorithms and initialization strategies with the TSVD and with the state of the art. Numerical results show that the new methods are efficient and competitive on both synthetic and real data.
- Abstract（参考訳）: 行列 $X$ と 2 つの階数 $r_1$ と $r_2$ が与えられたとき、アダマール分解 (HD) は 2 つの低階行列、$X_1$ の階数 $r_1$ と $X_2$ の階数 $r_2$ を求める。
ほとんどの場合、HD は truncated singular value decomposition (TSVD) のような標準的な低ランク近似よりも表現力が高く、同じ数のパラメータを持つ高階行列を表現できる。
本稿ではまず,HD に関する理論的知見,特に有用な再定式 $X\approx WH^\top$ ここでは$W$ と $H$ は$r_1 r_2$ 列を持ち,ある多様体に属する。
これにより、HDを計算するための3つの新しいアルゴリズムを開発できる。
最初は$X\approx X_1\circ X_2$という表現を使い、Manoptツールボックスに依存している。
他の2つは、$X\approx WH^\top$: 1つはブロック射影勾配法であり、もう1つは、実現可能な集合への射影を必要としない多様体ベースの勾配勾配アルゴリズムである。
最後の2つのアルゴリズムは、特に大きなスパースデータを扱うのに効果的である。
また,HDの精度を向上させるための新しい初期化を提案する。
アルゴリズムと初期化戦略をTSVDや最先端技術と比較する。
数値計算の結果,新しい手法は合成データと実データの両方において効率的かつ競合的であることがわかった。
関連論文リスト
- Well-conditioned iterative methods for large open quantum systems [1.2074552857379275]
マルコフの開量子系はリンドブラッド・マスター方程式 (ME) $fracmathrmdmathrmd t _t = MathcalL _t$ でモデル化されている。
本稿では、リンドブラッド方程式の一部が、いわゆるノージャンプ進化である$mathcalS$に対応して、効率的に逆転可能であることを示す。
論文 参考訳（メタデータ） (2026-08-31T14:22:05Z) - Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - 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) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチ行列を用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクが増加するにつれて改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。