論文の概要: High-Dimensional Procrustes Matching via Tree Counts

• arxiv url: http://arxiv.org/abs/2607.08538v1
• Date: Thu, 09 Jul 2026 14:33:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-10 14:45:27.566311
• Title: High-Dimensional Procrustes Matching via Tree Counts
• Title（参考訳）: 木数による高次元プロクリストマッチング
• Abstract要約: Procrustes matching problem(英語版)は、2つの集合を整列する$[n]$の未知の置換を復元するように要求する。 gtrsim maxlog n/d,sqrtlog n/n$ のとき、正確な回復が可能であることを示す。 また,木数計算アルゴリズムには条件2 > sqrt$ が必要であることを示唆する低次優位計算を行う。
• 参考スコア（独自算出の注目度）: 5.464035038606368
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose we observe two sets of $n$ Gaussian vectors in $\mathbb{R}^d$, with the promise that, after applying a permutation of $[n]$ and a rotation of $\mathbb{R}^d$, the two sets are $ρ$-correlated. The Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets. The problem is well-studied in the low-dimensional regime $d=O(\log n)$, but the high-dimensional regime $d\gg \log n$ has remained largely uncharted: prior matching guarantees require nearly perfect correlation $ρ=1-o(1)$, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as $d\ge \mathrm{polylog}(n)$, the algorithm succeeds with high probability for any $ρ^2>\sqrtα$, where $α\approx 0.338$ is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when $ρ^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $ρ^2 > \sqrtα$ is necessary for any tree-counting algorithm.
• Abstract（参考訳）: n$ガウスベクトルの 2 つの集合を $\mathbb{R}^d$ で観測すると、$[n]$ の置換と $\mathbb{R}^d$ の回転をすると、2 つの集合は $ρ$-関連である。 Procrustes マッチング問題は、2つの集合を整列する $[n]$ の未知の置換を復元するように要求する。 この問題は、低次元のレジーム $d=O(\log n)$ でよく研究されているが、高次元のレジーム $d\gg \log n$ は、ほとんど無チャートのままである。 本研究の主な成果は,定数相関で正確な回復を行う多項式時間アルゴリズムである。 このアルゴリズムは、'ワイド'ツリーの特別な選択された家系の重み付き数を計算し、比較することで機能する。 d\ge \mathrm{polylog}(n)$である限り、このアルゴリズムは任意の$ρ^2>\sqrtα$に対して高い確率で成功する。 我々は、このアルゴリズムの結果を改良された情報理論の保証で補完し、$ρ^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$で正確なリカバリが可能になることを示す。 また,木数計算アルゴリズムには$ρ^2 > \sqrtα$という条件が必要であることを示唆する低次優位計算を行う。

関連論文リスト

• A Simple Algorithm for Best Separable State [5.5559749120901385]
  本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
  論文  参考訳（メタデータ） (2026-08-10T19:04:15Z)
• Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests [27.444325804941773]
  本稿では,相関した $textErds-Rényi$ (ER) グラフペアモデルに基づくグラフマッチングについて検討する。 本稿では,n2+o(1)の時間複雑性を持つグラフマッチングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-07-10T04:08:08Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
  本研究では,一対のスパイクされたウィグナー行列における相関信号の検出と推定の計算タスクについて検討する。 アルゴリズムはスパイク間の相関を利用して、$X$から$x$を効率よく回収するか、$Y$から$y$を効率よく回収するかのどちらかが計算不可能な状態であっても信号を検出して推定することができる。
  論文  参考訳（メタデータ） (2025-11-08T15:23:44Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。 類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
  論文  参考訳（メタデータ） (2024-09-03T08:01:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
  正規化定数の計算における計算複雑性について検討する。 例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
  論文  参考訳（メタデータ） (2021-11-28T14:08:25Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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