論文の概要: Near-optimal fitting of ellipsoids to random points
- arxiv url: http://arxiv.org/abs/2208.09493v4
- Date: Thu, 1 Jun 2023 16:16:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-03 01:40:50.306201
- Title: Near-optimal fitting of ellipsoids to random points
- Title（参考訳）: 楕円体のランダム点への準最適嵌合
- Authors: Aaron Potechin, Paxton Turner, Prayaag Venkat, Alexander S. Wein
- Abstract要約: 楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
- 参考スコア（独自算出の注目度）: 68.12685213894112
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given independent standard Gaussian points $v_1, \ldots, v_n$ in dimension
$d$, for what values of $(n, d)$ does there exist with high probability an
origin-symmetric ellipsoid that simultaneously passes through all of the
points? This basic problem of fitting an ellipsoid to random points has
connections to low-rank matrix decompositions, independent component analysis,
and principal component analysis. Based on strong numerical evidence,
Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control,
pp. 6031-6036, 2013] conjecture that the ellipsoid fitting problem transitions
from feasible to infeasible as the number of points $n$ increases, with a sharp
threshold at $n \sim d^2/4$. We resolve this conjecture up to logarithmic
factors by constructing a fitting ellipsoid for some $n = \Omega( \,
d^2/\mathrm{polylog}(d) \,)$, improving prior work of Ghosh et al. [Proc. of
Symposium on Foundations of Computer Science, pp. 954-965, 2020] that requires
$n = o(d^{3/2})$. Our proof demonstrates feasibility of the least squares
construction of Saunderson et al. using a convenient decomposition of a certain
non-standard random matrix and a careful analysis of its Neumann expansion via
the theory of graph matrices.
- Abstract（参考訳）: 独立標準ガウス点 $v_1, \ldots, v_n$ in dimension $d$, for what value of $(n, d)$ は高確率で存在し、同時にすべての点を通過する原点対称楕円体が存在するか?
楕円体をランダムな点に当てはめるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析と関係している。
Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] の強い数値的証拠に基づいて、楕円体嵌合問題は、点数$n$が増加し、鋭い閾値が$n \sim d^2/4$となるにつれて、実現不可能から不可能へと遷移する。
我々はこの予想を、ある$n = \Omega( \, d^2/\mathrm{polylog}(d) \,)$ の適合楕円体を構築し、Ghosh et al の以前の仕事を改善することで対数的因子に分解する。
[コンピュータ科学の基礎シンポジウム, pp. 954-965, 2020]$n = o(d^{3/2})$.
我々の証明は、ある非標準確率行列の便利な分解とグラフ行列の理論によるノイマン展開の注意深い解析を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
関連論文リスト
- The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳（メタデータ） (2023-11-09T14:29:25Z) - 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) - Learning linear dynamical systems under convex constraints [4.4351901934764975]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。
後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
論文 参考訳（メタデータ） (2022-12-21T17:48:01Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - 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) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。