High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery

技術要約：一様ノルムにおける高次元疎な三角近似と、サンプリング回復への帰結

問題設定
本論文は、高次元の多変数関数の再構成における課題に取り組んでいる。このタスクは、限られた数の関数サンプルから行われるが、「次元の呪い」によってしばしば困難に直面する。著者らは、ウィーナー級数（Wiener classes）および混合滑らかさを持つベゾフ空間（Besov spaces）に属する関数の再構成を調査している。中心となる問題は、一様ノルム（$L_\infty$）における最良$m$項三角近似誤差の精密な境界を確立すること、およびこれらの境界が次元$d$に対してどのようにスケールするかを決定することである。最終的な目標は、これらの近似結果を非線形サンプリング回復（$m$個の関数値を用いる手法）のための保証へと変換し、$L_2$ノルムにおける当該問題の計算可能性を評価することである。

手法
著者らは、高次元における$L_q$近似と$L_\infty$近似の間の溝を埋めるために、3段階の戦略を採用している。

1. 確率的$L_q$近似： ウィーナー環 $A_\theta$（フーリエ係数の$\ell_\theta$可和性によって定義される）および関連するベゾフ空間に対し、著者らは$L_q$（$2 \le q < \infty$）における最良$m$項近似誤差の上界および下界を導出している。次元依存の定数を追跡せずに貪欲アルゴリズム（greedy algorithms）に依存していた従来の先行研究とは異なり、本論文では、ランダムな係数選択に基づく確率的手法（[19]に着想を得たもの）とベルンシュタインの不等式を利用している。これにより、誤差境界が$d$および$q$に対して多項式的にスケールすることを、定数を明示的に追跡することで示している。
2. 洗練されたニコルスキーの不等式： $L_q$の結果を（一様ノルムである）$L_\infty$へと拡張するために、著者らは古典的なニコルスキーの不等式の精緻化されたバージョン（定理3.1）を証明している。この不等式は、長方形領域 $[-N, N]^d$ 内の周波数を持つ三角多項式の$L_\infty$ノルムと$L_q$ノルムを関連付けるものである。極めて重要な点は、この不等式の定数が、適切な$q$（具体的には $q \sim \log(d)\log(\#Q)$）を選択した場合に、$d$に対して多項式的または対数的にしか増大しないよう制御されていることである。これにより、古典的な証明で見られる$d$に対する指数関数的な増大を回避している。
3. 補間と外挿： 補間議論（具体的には$K$-法およびハウスドルフ・ヤングの不等式）を用いることで、結果を異なるパラメータ領域（$\theta$および$q$）へと拡張している。最後に、確立された$L_\infty$近似境界を、非線形サンプリング数と最良$m$項近似誤差との既知の関係（[14]による）と組み合わせることで、サンプリング回復率を導出している。

主要な貢献と結果

• $L_q$近似のための精密な定数： 本論文は、最良$m$項近似幅 $\sigma_m(A_\theta; \mathcal{T}^d)_{L_q}$ に対する明示的な定数を提供している。$2 \le q < \infty$ かつ $0 < \theta \le 1$ の場合、上界は $C \sqrt{q} m^{-(1/\theta - 1/2)}$ と示され、定数 $C$ は次元 $d$ に依存しない（定理4.4）。下界についても、精密な定数とともに確立されている。
• 次元依存の$L_\infty$境界： 精緻化されたニコルスキーの不等式を用いて$L_q$の結果を組み合わせることで、著者らは一様ノルムに関する境界を導出している。サポートサイズ $\#Q$ を持つ三角多項式について、誤差は以下を満たす：
  $$\sigma_{4m}(t; \mathcal{T}^d)_{L_\infty} \lesssim \log(d)^{1/2} m^{-(1/\theta - 1/2)} (\log \#Q)^{1/2} \|t\|_{A_\theta}$$
  （定理4.5）。この結果は、次元 $d$ の影響が、サポートサイズに対する対数因子および $d$ に対する多項式因子に限定されていることを示している。
• ベゾフ空間への拡張： 知見は、支配的な混合滑らかさを持つベゾフ空間 $B^r_{p,\theta}$ へと拡張されている。限界混合滑らかさのケース $r = 1/\theta - 1/2$ において、本論文は、最良$m$項近似誤差が $L_\infty$ において $m^{-(1/\theta - 1/2)}$ の速度で減衰することを確立しており、次元依存性は $d \log(d)^{1/2}$ として現れる（定理5.3）。
• サンプリング回復への含意： 本論文は、これらの近似結果を$L_2$ノルムにおける非線形サンプリング数 $\varrho_m$ の境界へと変換している。[14]の相関関係を用いることで、これらの関数クラスにおいて、サンプリング回復誤差は $m$ に対して多項式的に減衰し、次元 $d$ への依存性は（パラメータに応じて）対数因子を除いて最大でも多項式的（具体的には $O(d^2)$ など）であることが示されている（系5.4）。これは、これらの特定の関数クラスに対するサンプリング回復問題の多項式的な計算可能性（polynomial tractability）を裏付けている。

意義と主張
著者らは、自らの研究が特定の疎な関数クラスに対する高次元サンプリング回復の「計算可能な（tractable）」解を提供すると主張している。主な意義は以下の通りである：

1. 次元性の制御： 本論文は、ウィーナー級数および関連するベゾフ級数の場合、次元の呪いを回避できることを示している。回復誤差は、次元 $d$ に対して指数関数的ではなく、多項式的に依存する。
2. 明示的な定数： 近似理論における多くの漸近的な結果とは異なり、本論文は近似幅に対して精密な、次元に依存しない（あるいは多項式的に依存する）定数を提供している。これは、実用的な応用や、厳密な計算可能性の結果を確立するために不可欠である。
3. 一様ノルムへの拡張： 著者らは、精緻化されたニコルスキーの不等式を用いることで、高次元における$L_q$近似と$L_\infty$近似の間の溝を、次元に関して完全に定量化された形で橋渡しすることに成功した。
4. 既存文献への補完： これらの結果は、Krieg [16] による最近の多項式的計算可能性の知見を補完し、[14] で確立された疎な三角近似と非線形サンプリング数の関係についての理解を洗練させるものである。

本論文は、$\ell_\theta$ 疎性（ここで $\theta \le 1$）を持つ関数については、次元の影響は管理可能であり、そのような関数の回復は高次元の設定においても（$\ell_1$ 最小化や関連する非線形手法を通じて）実現可能であると結論付けている。