技術的概要：確率的汎用サンプリング

1. 問題提起

本論文は、可分ヒルベルト空間 $\mathcal{H}$ 内の無限次元信号 $f$ を、有限個の測定値から再構成するという根本的な課題に取り組む。Adcock と Hansen によって導入された汎用サンプリング（GS）の枠組みは、任意のフレームまたはリース基底から要素を回復するための堅牢な決定論的手法を提供するが、深刻な基底依存の次元制約に悩まされている。

決定論的 GS において、安定した回復を保証するために必要な測定数 $m$ は、再構成次元 $n$ に対して二次的にスケールすることが多い（すなわち $m \gtrsim n^2$）。この「二次のボトルネック」は、サンプリング系（例えばフーリエ測定）と再構成系（例えばルジャンドル多項式）との間の幾何学的なミスマッチに起因し、数値的不安定性と悪条件化を引き起こす。本論文は、決定論的サンプリングから完全な確率的枠組みへの移行を通じて、この障壁を克服することを目指す。

2. 手法

著者らは、最初の $m$ 個のインデックスを決定論的に選択するのではなく、自然数上の特定の確率分布 $p = (p_j)_{j \in \mathbb{N}}$ に従って独立に測定インデックスを抽出する、ランダム化サンプリング戦略を提案する。

中核的構成要素：

• 重み付き最小二乗法： 再構成 $\tilde{f}$ は、重み付き最小二乗問題を解くことで得られる。ランダムなインデックス $\Omega = \{i_1, \dots, i_m\}$ が与えられたとき、この手法は以下の式を最小化する：
  $$\sum_{t=1}^m \frac{1}{p_{i_t}} |\langle W \iota_n x, s_{i_t} \rangle - \langle f, s_{i_t} \rangle|^2$$
  ここで、$\{s_k\}$ はサンプリング・フレーム、$\{w_k\}$ は再構成用リース基底（またはフレーム）、$\iota_n$ は $\mathbb{C}^n$ を $\ell^2$ に埋め込む写像である。
• レバレッジ・スコア・サンプリング： サンプリング効率を最適化するため、著者らは $p_j \propto \|v_j\|^2$ で定義されるレバレッジ・スコア分布を利用する。ここで $v_j = \iota_n^* U^* e_j$ は、サンプリング系と再構成系の間の相互作用を表す。この分布は、サンプル複雑性を支配するコヒーレンス・パラメータ $R$ を最小化する。
• 作用素論的解析： 解析は、2 つの主要な確率作用素の制御に依存する：
  1. 真のグラム行列 $\Sigma$ を推定する経験的グラム行列 $\hat{\Sigma}_\Omega$。
  2. 再構成部分空間外の信号成分（$P_{W_n}^\perp f$）によって引き起こされるエイリアシング誤差を支配する経験的交差項作用素 $\hat{C}_\Omega$。

理論的革新：

重要な方法論的貢献として、異なる無限次元ヒルベルト空間間で作用するランダムな長方形作用素に対する新たな行列ベルンシュタイン不等式の導出がある。この拡張により、著者らは無限次元設定におけるエイリアシング誤差の制御に不可欠な交差項作用素 $\hat{C}_\Omega$ の集中度を厳密に評価できるようになった。

3. 主要な貢献と結果

A. 普遍的な準線形サンプリング率

主要な理論的結果は、レバレッジ・スコア・サンプリングを採用することで、安定したサンプリング率が普遍的かつ準線形になることを確立する：
$$m \gtrsim n \log(2n/\delta)$$
ここで $\delta$ は失敗確率である。

• 普遍性： 決定論的 GS と異なり、この率は再構成空間がサンプリング空間に埋め込まれる（$W \subseteq S$）限り、サンプリング基底と再構成基底の具体的な選択に依存しない。
• 二次の障壁の克服： この結果は、互換性のない基底（例えばフーリエ - ルジャンドル対）に対する決定論的アプローチに内在する $m \gtrsim n^2$ の障壁を破る。

B. 誤差 bound と準最適性

本論文は、高い確率（$1-\delta$）で、再構成誤差が以下の式を満たすことを証明する：
$$\|f - \tilde{f}\| \leq \mu_{n,\Omega} \|P_{W_n}^\perp f\|$$
ここで $\|P_{W_n}^\perp f\|$ は、部分空間外の信号の尾部であり、最適な理論的近似誤差である。

• 安定性： 増幅係数 $\mu_{n,\Omega}$ は高い確率で有界である。
• 準最適性： 正規直交基底の場合、著者らは交差項因子 $K_{n,\Omega}$ が $m \to \infty$ とともに確率収束して 0 になることを証明する。その結果、再構成誤差は理論的下限に漸近的に近づき、準最適性を達成する。

C. フレームへの拡張

この枠組みは、再構成系が任意のフレーム（リース基底に限らない）である場合に一般化される。この設定では、極限グラム行列 $\Sigma$ が特異となる可能性がある。著者らは、モア - ペンローズ擬似逆行列を用いて再構成を定義し、経験的グラム行列が高い確率で $\Sigma$ と同じ値域を共有することを証明することで、冗長なフレームであっても安定した回復が可能であることを示した。

D. クリストッフェル・サンプリングとの関連

本論文は、離散的なレバレッジ・スコア分布を、重み付き最小二乗近似で用いられる連続的なクリストッフェル・サンプリング戦略と厳密に結びつける。正規直交設定において、レバレッジ・スコア・パラメータ $R$ がクリストッフェル・パラメータ $\kappa_w(P)$ と完全に一致することを示し、離散的な作用素枠組みと確立された連続近似理論を統合した。

4. 応用：フーリエ - ルジャンドル回復

実用的な有効性を示すため、著者らは、ルジャンドル多項式を用いて再構成を行う連続フーリエ測定から解析関数を回復するという古典的な問題にこの枠組みを適用した。

• 決定論的限界： 過去の決定論的研究では、この対は安定性のために $m \gtrsim n^2$ を必要とし、収束を根号指数率 $O(\rho^{-\sqrt{m}})$ に制限することが示されていた。
• 確率的結果： 導出されたレバレッジ・スコア分布（球ベッセル関数を用いて明示的に計算される）に従って周波数をサンプリングすることで、この手法は再構成次元 $n \sim m/\log m$ を達成する。
• 収束： これにより、決定論的な根号指数率よりも劇的に改善された準指数収束率 $O(\rho^{-m/\log m})$ が得られる。

5. 意義と主張

本論文は、任意のフレームに対応し、サンプル複雑性に関する明示的な非漸近的 bound を提供する、最初の厳密な確率的汎用サンプリング枠組みを確立すると主張する。

• 理論的影響： 無限次元空間間のランダムな長方形作用素に対するベルンシュタイン不等式の導出は、無限次元逆問題におけるエイリアシング誤差の制御を可能にするものとして、独立した関心を持つ貢献として提示されている。
• 実用的影響： この枠組みは、「幾何学的意識」を持ったランダム化を提供し、決定論的 GS の制限的な仮定を必要とせずに、フーリエ - ルジャンドル回復のような悪条件化された逆過程を安定化する。
• 限界と範囲： 著者らは控えめに、$n \log n$ の率は幾何学的包含 $W \subseteq S$ に依存していると指摘する。また、厳密な線形率（$m \gtrsim n$）を達成するには、i.i.d. サンプリングからの逸脱（例えば、貪欲法や決定論的点過程の使用）が必要であり、これには計算コストの増大や（RKHS のような）構造的制約をもたらすが、現在の抽象的枠組みは意図的にこれらを回避していると認めている。さらに、レバレッジ・スコア・サンプリングは基底のミスマッチと冗長性に対処するが、基礎となる物理的問題の内在的な不適切性（ill-posedness）を治すことはできないと明確にしている。

要約すると、この研究は、最適なレバレッジ・スコアに導かれた確率的サンプリングが、決定論的汎用サンプリングの二次的な次元制約を普遍的に克服し、準線形なサンプル複雑性で無限次元信号の安定かつ高精度な再構成を可能にすることを示している。