論文の概要: Phase transition of the Sinkhorn-Knopp algorithm

• arxiv url: http://arxiv.org/abs/2507.09711v1
• Date: Sun, 13 Jul 2025 17:07:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:23.860018
• Title: Phase transition of the Sinkhorn-Knopp algorithm
• Title（参考訳）: Sinkhorn-Knoppアルゴリズムの相転移
• Authors: Kun He,
• Abstract要約: Sinkhorn-Knoppアルゴリズムは$O(log n - log varepsilon)$と$widetildeO(n2)$timeでほぼ2倍の行列を生成する。 すべての$gamma 1/2$に対して、密度$gammaを持つ行列が存在し、アルゴリズムは$Omegaleft(n1/2/varepsilonright)$ iterationsを必要とする。
• 参考スコア（独自算出の注目度）: 8.271753306351684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The matrix scaling problem, particularly the Sinkhorn-Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best-known upper bound places it in the class of pseudopolynomial-time approximation algorithms. Meanwhile, the lower-bound landscape remains largely unexplored. Two fundamental questions persist: what accounts for the algorithm's strong empirical performance, and can a tight bound on its iteration count be established? For an $n\times n$ matrix, its normalized version is obtained by dividing each entry by its largest entry. We say that a normalized matrix has a density $\gamma$ if there exists a constant $\rho > 0$ such that one row or column has exactly $\lceil \gamma n \rceil$ entries with values at least $\rho$, and every other row and column has at least $\lceil \gamma n \rceil$ such entries. For the upper bound, we show that the Sinkhorn-Knopp algorithm produces a nearly doubly stochastic matrix in $O(\log n - \log \varepsilon)$ iterations and $\widetilde{O}(n^2)$ time for all nonnegative square matrices whose normalized version has a density $\gamma > 1/2$. Such matrices cover both the algorithm's principal practical inputs and its typical theoretical regime, and the $\widetilde{O}(n^2)$ runtime is optimal. For the lower bound, we establish a tight bound of $\widetilde{\Omega}\left(n^{1/2}/\varepsilon\right)$ iterations for positive matrices under the $\ell_2$-norm error measure. Moreover, for every $\gamma < 1/2$, there exists a matrix with density $\gamma$ for which the algorithm requires $\Omega\left(n^{1/2}/\varepsilon\right)$ iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold $\gamma = 1/2$.
• Abstract（参考訳）: 行列スケーリング問題、特にシンクホーン・ノックアルゴリズムは60年以上にわたって研究されてきた。 実際には、アルゴリズムはほんの数イテレーションで高品質な近似を生成することが多い。 しかし理論的には、最もよく知られた上界は擬ポリノミカル時間近似アルゴリズムのクラスに配置する。 一方、下界の風景はほとんど未探検のままである。 アルゴリズムの強い経験的性能と、その反復数に厳密な拘束力を持つものは何か、という2つの基本的な疑問が続いている。 $n\times n$ 行列の場合、その正規化バージョンは各エントリを最大のエントリで割ることで得られる。 正規化された行列は、ある定数$\rho > 0$が存在し、ある行または列がちょうど$\lceil \gamma n \rceil$エントリを持ち、少なくとも$\rho$の値を持ち、他の行や列は少なくとも$\lceil \gamma n \rceil$のようなエントリを持つような密度を持つ。 上界について、シンクホーン・ノックアルゴリズムは、正規化バージョンが密度$\gamma > 1/2$であるすべての非負の正方行列に対して、$O(\log n - \log \varepsilon)$ iterations and $\widetilde{O}(n^2)$ time でほぼ2倍確率行列を生成することを示す。 このような行列はアルゴリズムの主要な実用的な入力と典型的な理論的条件の両方をカバーし、$\widetilde{O}(n^2)$ランタイムは最適である。 下限については、$\ell_2$-norm 誤差測度の下で正行列に対する $\widetilde{\Omega}\left(n^{1/2}/\varepsilon\right)$ の厳密な境界を確立する。 さらに、すべての$\gamma < 1/2$に対して、密度$\gamma$を持つ行列が存在し、アルゴリズムは$\Omega\left(n^{1/2}/\varepsilon\right)$反復を必要とする。 要約すると、Sinkhorn-Knoppアルゴリズムにおける鋭い位相遷移は密度閾値$\gamma = 1/2$である。

関連論文リスト

• 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)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Improved quantum lower and upper bounds for matrix scaling [0.0]
  古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。 我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。 我々は低精度方式で改良された量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-09-30T17:29:23Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Quantum algorithms for matrix scaling and matrix balancing [9.010461408997646]
  行列スケーリングと行列バランシングは、様々な応用の2つの基本的な線形代数問題である。 これらの問題に対する量子アルゴリズムのパワーと限界について検討する。 Sinkhornの行列スケーリングアルゴリズムとOsborneの行列バランスアルゴリズムの2つの古典的手法の量子的実装を提供する。
  論文  参考訳（メタデータ） (2020-11-25T15:26:59Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)

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

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