Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

技術的サマリー：限られたセンサによる未知の高次元システムに対する証明可能な効率的なセンサ割当て

問題定義
本論文は、状態次元 $r$ が大きい未知の高次元線形動的システム ($x_{t+1} = Ax_t + Bu_t + w_t$) に対して、効率的なセンサ割当てを学習する課題に取り組む。目的は、データ収集段階で限られた数のセンサのみを用いて、システムが観測可能であることを保証する最小のセンサ集合（状態座標）を特定することである。

既存のアプローチはこの設定において、以下の 2 つの主要な限界に直面している：

1. モデル依存性: 古典的なセンサ割当て手法は、システム行列 ($A, B$) の正確な知識を必要とするが、未知システムではこれらは利用できない。
2. データ要件: 標準的なシステム同定（SYSID）手法は、通常、全状態観測（極めて高価）を必要とするか、あるいは既に観測性を保証する初期センサ割当ての存在を仮定している（循環的依存）。

手法
著者は、システムが制御可能かつ安定であるという仮定（仮定 1 および 2）の下で、これらの限界を克服するための 2 段階フレームワークを提案する。

• 段階 1：動的測定選択を伴うシステム同定
  著者は、全状態測定や既存の観測可能割当てを必要としない新しい SYSID アルゴリズム（アルゴリズム 1）を導入する。

  • データ収集: 全状態を同時に測定する代わりに、このアルゴリズムは $K$ 個の軌跡を収集する。各軌跡 $k$ において、少数のセンサ（$\bar{n}$）が、特定の（場合によっては異なる）状態座標の部分集合を測定する。
  • 測定戦略: 測定行列 $C_k$ は、すべての状態座標が少なくとも $s$ 個の軌跡で観測されるように（$s_{min} \ge 1$）、循環的に設計される。
  • 推定: アルゴリズムは、状態ダイナミクスの再帰的展開を利用して、状態を過去の入力の線形結合（マルコフパラメータ）として表現する。すべての軌跡にわたるこれらの入力 - 出力対に対して最小二乗回帰を行うことで、アルゴリズムはマルコフパラメータ行列 $G = [B, AB, \dots, A^dB]$ を推定する。
  • 復元: 推定ランク $d \ge r$ である場合、システム行列 $\hat{A}$ および $\hat{B}$ は、推定されたマルコフパラメータから疑似逆行列アプローチを用いて復元される。

• 段階 2：データ駆動型センサ割当て
  段階 1 で推定されたシステム行列を用いて、著者は最終的なセンサ集合を選択するために貪欲なセンサ割当てアルゴリズム（アルゴリズム 2）を適応させる。

  • ランク推定サブルーチン: 重要な構成要素は、ノイズを含む推定値 $\hat{A}$ を用いて観測性行列 $\mathcal{O}(\hat{C})$ のランクを推定するランク推定サブルーチン（アルゴリズム 3）である。このサブルーチンは、非ゼロ特異値とゼロ特異値を区別するために、推定誤差の境界に基づいて慎重に導出された閾値を採用する。
  • 貪欲選択: アルゴリズムは、観測性行列の推定されたランク増加を最大化する状態座標にセンサを反復的に追加し、フルランク（$r$）に達するまでこれを続ける。

• アクセス不能な座標への拡張
  このフレームワークは、特定の状態座標が物理的にセンサ配置にアクセスできないというシナリオに拡張される。アルゴリズムは探索空間をアクセス可能な座標に制限し、マルコフパラメータのアクセス可能な行から構築された推定ハンケル行列を用いてランク推定を行う（アルゴリズム 4）。

主要な貢献と理論的結果

1. SYSID に対する非漸近的誤差境界: 本論文は、提案された SYSID アルゴリズムに対する有限サンプル保証を提供する。定理 1 は、マルコフパラメータ推定の誤差が $\tilde{O}(\sqrt{md/(s_{min}T)})$ として減少することを示している。ここで、$m$ は入力次元、$d$ は推定ランク、$T$ は軌跡長、$s_{min}$ は任意の状態が観測される最小回数である。重要なのは、十分な数の軌跡が収集されれば、単一のセンサ（$\bar{n}=1$）であってもこれが成り立つことである。
2. センサ割当ての保証: 定理 2 および定理 3 は、提案された 2 段階フレームワークが観測性を保証するセンサ割当てをもたらすことを証明する。使用されるセンサ数 $\hat{n}$ は、$(1 + \log(r))n^*$ によって有界であり、ここで $n^*$ は必要な最適最小センサ数である。この近似比は、既知のシステムに対する既知の最良の結果と一致し、学習された近似モデル上で動作しているにもかかわらず達成されている。
3. アクセス不能性への頑健性: このフレームワークは、アクセス可能な座標が観測性を保証するのに十分であれば（仮定 3）、アクセス不能な状態座標を持つシステムを正常に処理する。

実験的検証
著者は、2 つのモデルに対する数値実験を通じてアプローチを検証した：

• ブロック循環システム: 観測性にはブロックごとに 1 つのセンサが必要となるシステム。アルゴリズムはシステムパラメータを正常に学習し、5 つのセンサの最適割当てを特定した。
• 熱力学（HVAC）: 5 つのアクセス不能な座標を持つ 20 ゾーンシステム。アルゴリズムはアクセス可能な測定のみを使用してダイナミクスを学習し、観測性を保証するために 10 つのセンサ（ブロックあたり 2 つ）の最適割当てを特定した。

意義
本論文は、既知モデルを仮定する理論的センサ割当てと、しばしば完全な観測性を欠く実用的なデータ駆動制御との間のギャップを埋めると主張している。システム同定プロセスを全状態観測性の要件から切り離すことで、提案手法は、センサが希少、高価、または特定の場所に制限されている高次元システムに対して、効率的なセンサ構成の学習を可能にする。非漸近的保証は、電力網、気象予報、神経科学などの安全クリティカルなアプリケーションにおける、これらのデータ駆動型割当ての信頼性に対する理論的基盤を提供する。