技術的概要：一般化された行列近接問題 II

問題定義

本論文は、[13] で最初に扱われた一般化された行列近接問題の研究を拡張する。基本的な問題は、特定の制約の下で与えられた行列 $A$ への距離を最小化する行列 $X$ を求めるものである。ここで考慮される一般化された形式は、3 つの与えられた行列 $A, B, C$ を含み、以下の目的関数を最小化する：
$$\min_{X \in S} \|A - BXC\|$$
ここで、$S$ はランク、ノルム、対称性、構造、正値性などのさまざまな制約によって定義される実行可能集合を表す。本論文は、[13] に見られる標準的なフロベニウスノルム定式化 ($\|\cdot\|_F$) に対する 3 つの拡張を具体的に調査する：

1. アフィン項： $dx^TE$ や $Dxe^T$ などのアフィン項を目的関数に組み込むこと。
2. クロネッカー積： 標準的な行列積をクロネッカー積（例：$B \otimes X \otimes C$）に置き換え、ランク制約をクロネッカーランクに一般化すること。
3. シャトーンノルム： フロベニウスノルムを任意の直交不変ノルム、特にシャトーン $p$-ノルム ($\|\cdot\|_{\sigma,p}$) に一般化すること。

手法

本論文は、特定のケースに対する閉形式解の導出と、一般的なケースに対するゼロ次反復アルゴリズムの開発という二重のアプローチを採用している。

1. 閉形式解

著者は、[13] の結果を拡張する、閉形式解を許容する問題の 4 つの特定のバリアントを特定している：

• アフィン一般化近接： $\|A - BXC + Dxe^T\|_F$ などの項を含む問題。これらは射影演算子を用いて標準的な一般化近接問題に変換される（命題 3.2）。
• 分離可能クロネッカー積： $\|A - B \otimes X \otimes C\|_F$ の最小化。これは、クロネッカー構造を標準的な行列近接問題に変換する並べ替え演算子 $R$ を導入することで解かれる（命題 3.3）。
• 一般化クロネッカーランク： $\text{rank}_\otimes(X) \le r$ の制約の下で $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ の最小化。これは、並べ替え演算子とクロネッカー積の特異値分解 (SVD) の性質を通じて、標準的なランク制約問題に帰着される（命題 3.4、アルゴリズム 1）。
• 指定された部分トレース： 部分トレース制約 $\text{tr}_P(X(W \otimes I)) = \lambda W$ の下で $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ の最小化。これは、指定された固有値問題またはランク制約問題に帰着される（命題 3.5、系 3.6）。

2. ミルスキー型結果の非存在

本論文は、最良のランク-$r$ 近似が使用される直交不変ノルムに依存しないというエッカート・ヤング・ミルスキーの定理が、一般化された問題 $\min_{\text{rank}(X) \le r} \|A - BXC\|$ に拡張されるかどうかを調査する。

• 結果： 著者は、$B$ と $C$ が単位行列でない場合、ミルスキー型結果は成立しないことを証明する。
• 証拠： 反例（例 4.2）を通じて、ランク制約付き一般化問題の最小化解は、選択された特定のシャトーンノルム ($p=1, 2, \infty$) に依存することを示す。これは、すべての直交不変ノルムに対して解が普遍的である標準的なランク近似問題とは対照的である。

3. 反復アルゴリズム（アルゴリズム 3）

閉形式解が存在しない場合（特に一般的なシャトーンノルムと複雑な制約に対して）、著者はディクストラの射影法（アルゴリズム 2）に基づき、シャトーンノルムに特化した反復アルゴリズム（アルゴリズム 3）を提案する。

• メカニズム： アルゴリズムは 2 つのステップを交互に実行する：
  1. $X$-更新： フロベニウスノルムにおける一般化行列近接問題を解く（[13] の手法または第 3 節で導出された閉形式解を使用）。
  2. $Y$-更新： シャトーンノルム $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$ に対する近接作用素問題を解く。著者は、$p=1$（核ノルム）、$p=\infty$（スペクトルノルム）、および一般的な $p \in (1, \infty)$ に対する $Y$ の特異値の明示的な閉形式更新式を導出する（補題 5.5–5.7）。
• 主要な特徴： このアルゴリズムはゼロ次であり、明示的な勾配または部分勾配を計算しない。これは、数値線形代数操作（SVD と行列乗算）のみに依存する。
• 収束性： このアルゴリズムは、任意の初期点から大域的最小解へ収束することが証明されている。収束率は（$p \neq 2$ におけるシャトーンノルムの強凸性の欠如により）準線形であるが、数値実験では実際には準線形に近い挙動を示すことが示唆されている。

主要な結果

• 閉形式展開： 本論文は、一般化近接問題のアフィン、分離可能クロネッカー、クロネッカーランク、および部分トレースのバリアントに対する明示的な解を提供する。
• 理論的限界： 異なる直交不変ノルムに対する解の普遍性（ミルスキーの定理）が、非単位行列の乗数 $B$ と $C$ の存在下で崩壊することを確立する。
• アルゴリズムのパフォーマンス：
  • 速度： 数値実験（第 6 節）において、アルゴリズム 3 は汎用凸最適化ソルバー（特に SCS ソルバーを備えた CVX）を大幅に凌駕する。大規模な次元において、CVX はしばしば合理的な時間制限内で収束に失敗するのに対し、アルゴリズム 3 は急速に収束する。
  • 精度： アルゴリズム 3 は前方誤差において機械精度 ($\approx 10^{-15}$) を達成するのに対し、CVX は変動する誤差（$10^{-7}$ から $10^3$ の範囲）を示し、しばしば制約（例えばシステム同定タスクにおける制約）を満たすことに失敗する。
  • 汎用性： このアルゴリズムは、CVX などの標準ソルバーではアクセス不可能な非標準的な凸目的関数（例：シャトーン $3/2$-ノルム）および非凸制約（例：ランク制約、指定された固有値）を成功裡に処理する。

意義と主張

本論文は、以下の点で行列近接問題の分野を進展させると主張している：

1. 解可能性の拡張： アフィン項とクロネッカー構造を含む新しいクラスの問題に対する閉形式解を提供する。
2. 理論的境界の明確化： 古典的な近似定理（ミルスキー）を一般化された設定に拡張することの限界を実証する。
3. 堅牢な代替案の提供： 大域収束性を持ち、勾配不要であり、汎用ソルバーよりも計算的に優れている反復アルゴリズムを提案する。
4. 構造利用の強調： 著者は、数値線形代数を通じて特定の行列構造を利用すること（[13] および本論文で行われているように）が、汎用凸最適化フレームワークのみに依存するよりも、優れたパフォーマンスと（非凸ケースを含む）広範な適用性をもたらすと強調している。

本論文は [13] の続編として提示され、微分計算なしで最適化問題を解決するという哲学を維持し、行列空間の豊かな構造を活用している。