論文の概要: Dimension-free Remez Inequalities and norm designs
- arxiv url: http://arxiv.org/abs/2310.07926v5
- Date: Wed, 20 Dec 2023 18:35:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 03:34:56.862558
- Title: Dimension-free Remez Inequalities and norm designs
- Title(参考訳): 次元フリー remez の不等式とノルム設計
- Authors: Lars Becker, Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang
- Abstract要約: ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。
ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
- 参考スコア(独自算出の注目度): 48.5897526636987
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The classical Remez inequality bounds the supremum of a bounded-degree
polynomial on an interval $X$ by its supremum on any subset $Y\subset X$ of
positive Lebesgue measure.
There are many multivariate generalizations of the Remez inequality, but most
have constants that depend strongly on dimension.
Here we show that a broad class of domains $X$ and test sets $Y$ -- termed
\emph{norm designs} -- enjoy dimension-free Remez-type estimates.
Instantiations of this theorem allow us for example \emph{a}) to bound the
supremum of an $n$-variate degree-$d$ polynomial on the solid cube $[0,1]^n$ by
its supremum on the regular grid $\{0,1/d,2/d,\ldots, 1\}^n$ independent of
dimension; and \emph{b}) in the case of a degree-$d$ polynomial
$f:\mathbf{Z}_K^n\to\mathbf{C}$ on the $n$-fold product of cyclic groups of
order $K$, to show the supremum of $f$ does not increase by more than
$\mathcal{O}(\log K)^{2d}$ when $f$ is extended to the polytorus as
$f:\mathbf{T}^n\to\mathbf{C}$.
- Abstract(参考訳): 古典的 Remez の不等式は、任意の部分集合 $Y\subset X$ の正のルベーグ測度上の上限で、境界次多項式の上限を区間 $X$ で有界とする。
レメス不等式には多変量一般化が多数存在するが、その多くは次元に強く依存する定数を持つ。
ここで、x$ と test の広いクラスが \emph{norm design} と呼ばれる $y$ を設定していることを示す。
Instantiations of this theorem allow us for example \emph{a}) to bound the supremum of an $n$-variate degree-$d$ polynomial on the solid cube $[0,1]^n$ by its supremum on the regular grid $\{0,1/d,2/d,\ldots, 1\}^n$ independent of dimension; and \emph{b}) in the case of a degree-$d$ polynomial $f:\mathbf{Z}_K^n\to\mathbf{C}$ on the $n$-fold product of cyclic groups of order $K$, to show the supremum of $f$ does not increase by more than $\mathcal{O}(\log K)^{2d}$ when $f$ is extended to the polytorus as $f:\mathbf{T}^n\to\mathbf{C}$.
関連論文リスト
- An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
有限体 $mathbbF_q2$ は$q2$ 要素からなる。
まず、いくつかの重要な単純化を取り入れた電力関数 $f(x) = xq+2$ on $mathbbF_q2$ の微分スペクトルを決定する方法を提案する。
論文 参考訳(メタデータ) (2024-07-08T14:01:06Z) - Some new infinite families of non-$p$-rational real quadratic fields [0.0]
同時に、$p_j$-有理実体の無限族を構成するための単純な方法論を与え、$p_j$の任意の上を無理化する。
これらの技法の1つの特徴は、素体$K=mathbbQ(sqrtD)$を、極大アーベル群のガロア群のトーション群の$p$パワー巡回成分である$p$を超える非有理な外部素数の$K$が$paであるような体を与えるのに使用できることである。
論文 参考訳(メタデータ) (2024-06-20T18:00:51Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳(メタデータ) (2023-01-04T04:15:40Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳(メタデータ) (2022-09-04T10:01:39Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳(メタデータ) (2022-06-23T16:23:59Z) - Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
mathbb Cd$ の正則基底の集合 $k$ は互いに非バイアスな $|langle e,frangle |2 = 1/d$ と呼ばれ、$e$ と $f$ は異なる基底の基底ベクトルである。
この対称性を(解析的に)利用して、半定値プログラムのサイズを縮小し、取り外し可能とする。
論文 参考訳(メタデータ) (2021-11-10T14:14:53Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳(メタデータ) (2020-04-15T06:18:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。