論文の概要: Equiangular lines via matrix projection
- arxiv url: http://arxiv.org/abs/2110.15842v2
- Date: Mon, 20 Mar 2023 19:43:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 05:51:25.654199
- Title: Equiangular lines via matrix projection
- Title(参考訳): 行列投影による等角線
- Authors: Igor Balla
- Abstract要約: 1973年、Lemmens と Seidel は、角 $arccos(alpha)$ の等角線の最大数を $mathbbRr$ で決定する問題を提起した。
最近のブレークスルーはこの問題のほぼ完全な解決に繋がった。
本稿では,従来のアプローチを統一し,改善する上界を求める新しい手法を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In 1973, Lemmens and Seidel posed the problem of determining the maximum
number of equiangular lines in $\mathbb{R}^r$ with angle $\arccos(\alpha)$ and
gave a partial answer in the regime $r \leq 1/\alpha^2 - 2$. At the other
extreme where $r$ is at least exponential in $1/\alpha$, recent breakthroughs
have led to an almost complete resolution of this problem. In this paper, we
introduce a new method for obtaining upper bounds which unifies and improves
upon previous approaches, thereby bridging the gap between the aforementioned
regimes, as well as significantly extending or improving all previously known
bounds when $r \geq 1/\alpha^2 - 2$. Our method is based on orthogonal
projection of matrices with respect to the Frobenius inner product and it also
yields the first extension of the Alon-Boppana theorem to dense graphs, with
equality for strongly regular graphs corresponding to $\binom{r+1}{2}$
equiangular lines in $\mathbb{R}^r$. Applications of our method in the complex
setting will be discussed as well.
- Abstract(参考訳): 1973年、lemmens と seidel は、角 $\arccos(\alpha)$ を持つ$\mathbb{r}^r$ の等角線の最大数を決定する問題を提起し、r \leq 1/\alpha^2 - 2$ というレジームにおいて部分的な答えを与えた。
一方、$r$が少なくとも1/alpha$で指数関数的である場合、最近のブレークスルーはこの問題のほぼ完全な解決につながった。
本稿では,従来のアプローチを統一し,改善する上界を得るための新しい手法を提案する。これにより,前述の政権間のギャップを埋めるとともに,$r \geq 1/\alpha^2 - 2$の場合に,既知境界をすべて拡張あるいは改善する。
この方法はフロベニウスの内積に対する行列の直交射影に基づいており、さらに、アロン・ボッパナの定理の高密度グラフへの最初の拡張をもたらし、$\mathbb{R}^r$における$\binom{r+1}{2}=等角線に対応する強い正則グラフに対する等式も得られる。
本手法の複雑な設定における応用についても考察する。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳(メタデータ) (2024-01-14T14:14:19Z) - Solving Dense Linear Systems Faster than via Preconditioning [15.781447266000159]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳(メタデータ) (2023-11-03T14:56:24Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳(メタデータ) (2023-10-27T16:54:29Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Spectrum of inner-product kernel matrices in the polynomial regime and
multiple descent phenomenon in kernel ridge regression [3.997680012976965]
カーネル行列はその次数-$ell$近似によってよく近似される。
行列のスペクトルが分布に収束することを示す。
論文 参考訳(メタデータ) (2022-04-21T22:20:52Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Tight High Probability Bounds for Linear Stochastic Approximation with
Fixed Stepsize [41.38162218102825]
本稿では,線形近似 (LSA) アルゴリズムの漸近的解析を行う。
我々は、より弱い条件下での LSA の性能に高い確率境界を導出する:$(bf A_n, bf b_n): n in mathbbN*$。
bf A_n: n in mathbbN*$ {\displaystyle \mathbbN*=} の列について追加の仮定なしでは、我々の結論は改善できないことを示す。
論文 参考訳(メタデータ) (2021-06-02T16:10:37Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳(メタデータ) (2021-01-29T18:57:52Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。