論文の概要: 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$ を満たし、量子論に独立した興味を持つような場合である。
さらに,提案手法を用いてウェルチ境界の改善を行った。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks [46.04785603483612]
我々はネステロフの加速勾配が複雑性$O(kappalogfrac1epsilon)$に達することを証明している。
特に,NAGが線形収束速度を加速できることを示す。
論文 参考訳（メタデータ） (2024-10-12T20:33:37Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - 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) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。