論文の概要: Equiangular lines and regular graphs
- arxiv url: http://arxiv.org/abs/2110.15842v1
- Date: Fri, 29 Oct 2021 15:06:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 22:49:43.643697
- Title: Equiangular lines and regular graphs
- Title(参考訳): 等角線と正則グラフ
- Authors: Igor Balla
- Abstract要約: 複素等角線に対して、共通なエルミート角 $arccos(alpha)$ を持つ$mathbbCr$ の不等式を証明する。
また、複素等角線の最大数に対する最初の普遍境界は、共通のエルミート角 $arccos(alpha)$ で$mathbbCr$ である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In 1973, Lemmens and Seidel posed the problem of determining $N_\alpha(r)$,
the maximum number of equiangular lines in $\mathbb{R}^r$ with common angle
$\arccos(\alpha)$. Recently, this question has been almost completely settled
in the case where $r$ is large relative to $1/\alpha$, with the approach
relying on Ramsey's theorem. In this paper, we use orthogonal projections of
matrices with respect to the Frobenius inner product in order to overcome this
limitation, thereby obtaining upper bounds on $N_{\alpha}(r)$ which
significantly improve on the only previously known universal bound of Glazyrin
and Yu, as well as taking an important step towards determining $N_\alpha(r)$
exactly for all $r, \alpha$. In particular, our results imply that $N_\alpha(r)
= \Theta(r)$ for $\alpha \geq \Omega(1/r^{1/5})$.
Our arguments rely on a new geometric inequality for equiangular lines in
$\mathbb{R}^r$ which is tight when the number of lines meets the absolute bound
$\binom{r+1}{2}$. Moreover, using the connection to graphs, we obtain lower
bounds on the second eigenvalue of the adjacency matrix of a regular graph
which are tight for strongly regular graphs corresponding to $\binom{r+1}{2}$
equiangular lines in $\mathbb{R}^r$. Our results only require that the spectral
gap is less than half the number of vertices and can therefore be seen as an
extension of the Alon-Boppana theorem to dense graphs.
Generalizing to $\mathbb{C}$, we also obtain the first universal bound on the
maximum number of complex equiangular lines in $\mathbb{C}^r$ with common
Hermitian angle $\arccos(\alpha)$. In particular, we prove an inequality for
complex equiangular lines in $\mathbb{C}^r$ which is tight if the number of
lines meets the absolute bound $r^2$ and may be of independent interest in
quantum theory. Additionally, we use our projection method to obtain an
improvement to Welch's bound.
- Abstract(参考訳): 1973年、lemmens と seidel は、共通角度 $\arccos(\alpha)$ を持つ$\mathbb{r}^r$ の等角線の最大数である $n_\alpha(r)$ を決定する問題を提起した。
近年、r$ が 1/\alpha$ に対して大きい場合、ラムゼーの定理に依拠するアプローチにおいて、この問題はほぼ完全に解決されている。
本稿では、この制限を克服するために、フロベニウス内積に関する行列の直交射影を用いて、以前に知られているグラジリンとユの普遍境界において著しく改善された$N_{\alpha}(r)$の上界を得るとともに、すべての$r, \alpha$に対して$N_\alpha(r)$を正確に決定するための重要なステップを取る。
特に、結果は$n_\alpha(r) = \theta(r)$ for $\alpha \geq \omega(1/r^{1/5})$ であることを示している。
我々の議論は、線数が絶対有界$\binom{r+1}{2}$を満たすとき、強である$\mathbb{R}^r$の等角線に対する新しい幾何学的不等式に依存する。
さらに、グラフへの接続を用いて、$\binom{r+1}{2}$等角線に対応する強正則グラフに対して、$\mathbb{r}^r$ の強正則グラフの隣接行列の第2固有値の下限を求める。
この結果は、スペクトルギャップが頂点数の半分以下であることしか必要とせず、アロン・ボッパナの定理の高密度グラフへの拡張と見なすことができる。
また、$\mathbb{c}$ に一般化すると、共通エルミート角 $\arccos(\alpha)$ を持つ$\mathbb{c}^r$ の複素等角線の最大数上の最初の普遍境界を得る。
特に、複素等角線に対する不等式を$\mathbb{c}^r$ で証明するが、これは直線数が絶対値 $r^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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。