論文の概要: On a minimum enclosing ball of a collection of linear subspaces
- arxiv url: http://arxiv.org/abs/2003.12455v1
- Date: Fri, 27 Mar 2020 15:00:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-19 05:38:18.707065
- Title: On a minimum enclosing ball of a collection of linear subspaces
- Title（参考訳）: 線形部分空間の集合の最小囲い球について
- Authors: Timothy Marrinan, P.-A. Absil, Nicolas Gillis
- Abstract要約: 本稿では、線型部分空間の集合のミニマックス中心について述べる。
ミニマックスセンターのランクによってパラメータ化される最適化問題を提案・解決する。
目的を拡大し、ランク=k$ミニマックス中心で失われた情報をペナライズすることにより、最適な次元である$k*$と中心部分空間である$U* in$Gr$(k*,n)$を最小囲み球の中心で共に回収する。
- 参考スコア（独自算出の注目度）: 16.466372560527827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper concerns the minimax center of a collection of linear subspaces.
When the subspaces are $k$-dimensional subspaces of $\mathbb{R}^n$, this can be
cast as finding the center of a minimum enclosing ball on a Grassmann manifold,
Gr$(k,n)$. For subspaces of different dimension, the setting becomes a disjoint
union of Grassmannians rather than a single manifold, and the problem is no
longer well-defined. However, natural geometric maps exist between these
manifolds with a well-defined notion of distance for the images of the
subspaces under the mappings. Solving the initial problem in this context leads
to a candidate minimax center on each of the constituent manifolds, but does
not inherently provide intuition about which candidate is the best
representation of the data. Additionally, the solutions of different rank are
generally not nested so a deflationary approach will not suffice, and the
problem must be solved independently on each manifold. We propose and solve an
optimization problem parametrized by the rank of the minimax center. The
solution is computed using a subgradient algorithm on the dual. By scaling the
objective and penalizing the information lost by the rank-$k$ minimax center,
we jointly recover an optimal dimension, $k^*$, and a central subspace, $U^*
\in$ Gr$(k^*,n)$ at the center of the minimum enclosing ball, that best
represents the data.
- Abstract（参考訳）: 本稿では、線型部分空間の集合のミニマックス中心について述べる。
部分空間が$k$ 次元の $\mathbb{R}^n$ の部分空間であるとき、これはグラスマン多様体上の最小閉球の中心である Gr$(k,n)$ を見つけるものとしてキャストできる。
異なる次元の部分空間に対して、設定は単一の多様体ではなくグラスマン多様体の非連結和となり、問題はもはや十分に定義されていない。
しかし、これらの多様体の間には、写像の下の部分空間の像に対する距離の明確な概念を持つ自然な幾何学的写像が存在する。
この文脈で最初の問題を解決すると、各構成多様体上の候補ミニマックス中心となるが、本質的にどの候補がデータの最良の表現であるかの直観は提供されない。
さらに、異なる階数の解は一般にネストされないので、デフレショナルアプローチは十分ではなく、各多様体で独立に解かなければならない。
ミニマックスセンターのランクによってパラメータ化される最適化問題を提案・解決する。
この解は双対上の準次アルゴリズムを用いて計算される。
目的を拡大し、ランク=k$ミニマックス中心が失った情報をペナライズすることにより、最適な次元である$k^*$と中心部分空間である$U^* \in$Gr$(k^*,n)$を最小囲み球の中心で共に回収し、そのデータを表現する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - On Generalization Bounds for Projective Clustering [3.4490841399255823]
ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
論文 参考訳（メタデータ） (2023-10-13T14:15:54Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。
ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。
また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
論文 参考訳（メタデータ） (2021-10-18T02:57:25Z) - Randomized Dimensionality Reduction for Facility Location and
Single-Linkage Clustering [13.208510864854894]
ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。
本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
論文 参考訳（メタデータ） (2021-07-05T05:55:26Z) - Geometry of the Loss Landscape in Overparameterized Neural Networks:
Symmetries and Invariances [9.390008801320024]
それぞれに1つの余分なニューロンを加えると、以前の離散ミニマを1つの多様体に接続するのに十分であることを示す。
対称性によって誘導される臨界部分空間の数が、大域ミニマ多様体を構成するアフィン部分空間の数を支配していることを示す。
論文 参考訳（メタデータ） (2021-05-25T21:19:07Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳（メタデータ） (2020-08-06T09:50:29Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。