論文の概要: The sharp SAT/UNSAT phase transition in random ellipsoid fitting

• arxiv url: http://arxiv.org/abs/2608.10184v1
• Date: Mon, 10 Aug 2026 19:55:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:45.801357
• Title: The sharp SAT/UNSAT phase transition in random ellipsoid fitting
• Title（参考訳）: ランダム楕円体フィッティングにおけるシャープSAT/UNSAT相転移
• Abstract要約: エンフェレプソイド整合は行列 $S succeq 0$ であり、すべての$i$に対して$x_itop S x_i =d$ となる。 我々は、ソーンダーソン、パリロ、ウィルスキーの予想を証明し、$n,d を infty$ にすると、この半確定実現可能性問題は $n sim d2/4$ で急移行する。
• 参考スコア（独自算出の注目度）: 5.7652356955571085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = α^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[λ_- , λ_+] \subset (0,\infty)$ depending only on $α^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.
• Abstract（参考訳）: x_1,\ldots,x_n$ を $\mathbb{R}^d$ の独立標準ガウスベクトルとする。 \emph{ellipsoid fit} は、すべての$i$に対して$x_i^\top S x_i = d$ となるような行列 $S \succeq 0$ であるので、すべての点が中心の楕円体 $\{ x : x^\top S x = d\}$ の境界上にある。 Saunderson, Parrilo and Willsky は、$n,d \to \infty$ として、この半確定実現可能性問題は、$n \sim d^2/4$ で急な遷移を行うと推測した。 私たちはこの予想を証明する。 もし$\lim \sup n/d^2 = α^* <1/4$ であれば、確率が 1 に比例するエリプシド適合式が存在し、また、固定間隔$[λ_-, λ_+] \subset (0,\infty)$ ですべての固有値を持つ$S$を選択できる。 逆に、$\lim \inf n/d^2 > 1/4$ ならば、確率が 1 になるような楕円体は、スペクトル制限なしに存在しない。 我々の証明は、Bandeira と Maillard (2025) によって開発されたガウス同値フレームワークに基づいており、その作業で残された2つのギャップを閉じている。 満足度側では、新しい材料は二重ベクトルのヘッドテール分解、スパースヘッド制約の正確な補正、低影響テールのガウス比較原理である。 満足できない面では、候補を低ランクスペクトルヘッドとシャッテン3拡散バルクに分割し、頭部のバルク条件をガウス化し、投影されたゴードンエスケープ引数を適用する。 閾値は正半定円錐の統計次元$d(d+1)/4$で制御される。

関連論文リスト

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
  我々はGPUを使用して、$mathbbC,$mathbbR,$ $mathbbF_p$および$mathbbQ.$以上の永久体の計算を劇的に高速化する。 我々は、一元群における恒久的な測地学について研究する。 恒等式から$n$-サイクル置換行列への測地論について、普遍スケーリング関数 $f(t)=frac1nln|perm((t))|$ は$n$ in とは独立である。
  論文  参考訳（メタデータ） (2026-02-08T22:31:42Z)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors [47.927989749887864]
  我々は、$s$sparseベクトルの最低ケース次元削減を超越して研究する。 任意の集合 $X$ of $s$-sparse vectors in $mathbbRO(s2)$ に対して、$mathbbRO(s2)$ への線型写像が存在し、任意の $ell_p$ ノルムにおいて$X$の99%のベクトルのノルムを正確に保存する。 我々は、$f$の非線形性と$の非負性の両方を示す。
  論文  参考訳（メタデータ） (2025-02-27T08:17:47Z)
• Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
  問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。 任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
  論文  参考訳（メタデータ） (2023-07-03T17:46:23Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。 ラプラシアン滑らか化が多様体適応であることを証明する。
  論文  参考訳（メタデータ） (2021-06-03T01:20:41Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)
• Extremal elements of a sublattice of the majorization lattice and approximate majorization [0.0]
  一般に、極値確率ベクトルは、閉じた球に対して$mathcalBp_epsilon(x)$に対して1pinfty$で存在しないことを示す。 また、ボールの半径と中心の点から、これらの極端要素を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-01-23T19:09:18Z)

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

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