An NPDo Approach for Tensor Block-Diagonalization

技術的概要：テンソルブロック対角化のための NPDo 手法

問題定義
本論文は、**主テンソルブロック対角化（PTBD）**の問題を取り扱う。$m$-モードテンソル $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$ が与えられたとき、$m$ 個の直交行列 $P_\ell \in \text{St}(k_\ell, n_\ell)$（ここで $\text{St}$ は複素シュティフェル多様体を表す）の集合を見出し、変換されたテンソル $\mathcal{T} = \mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H$ がそのブロック対角成分に最適に集中するようにする。

この問題は、$\|\text{BDiag}_{(\tau_{k_1}, \dots, \tau_{k_m})}(\mathcal{T})\|_F^2$ で表される $\mathcal{T}$ のブロック対角部分のフロベニウスノルムを最大化する形で定式化される。ここで $\tau_{k_\ell}$ はモード次元の特定の分割を表す。この定式化は、既存のいくつかのテンソル分解を一般化する：

• 主テンソル SVD（PT-SVD）： 各ブロックサイズが $1 \times 1 \times \dots \times 1$ である場合に生じる。
• Tucker 分解（TD）： モードあたりブロックが 1 つ（$t=1$）の場合に生じる。
• ランク 1 近似： すべての $k_\ell = 1$ である特殊な場合。

近似低ランク表現を求めることが多い標準的なテンソル分解とは異なり、PTBD は、特定のブロック対角構造内で捕捉されるエネルギーを最大化する最適な直交変換を求める。

手法
著者らは、結果として生じる非凸最適化問題を解くための**NPDo（直交極因子依存性を有する非線形極分解）**手法を提案する。

1. 最適化定式化： 問題は結合されたトレースの和を最大化する問題として定式化される。最適性に関するカルーシュ・クーン・タッカー（KKT）条件は、$m$ 個の結合された極分解方程式の系へと導かれる。具体的には、停留点において、目的関数の各 $P_\ell$ に関する偏ユークリッド勾配は $P_\ell \Lambda_\ell$ に等しくなければならない。ここで $\Lambda_\ell$ はエルミート半正定値行列である。
2. 交互 SCF アルゴリズム（アルゴリズム 3.1）： 中核となる手法は、ガウス・ザイデル型更新を伴う交互自己無撞着場（SCF）反復である。各ステップで、他の行列を固定したまま 1 つの行列 $P_\ell$ を更新する。更新には、偏勾配 $H_\ell$ を計算し、薄型特異値分解（SVD）を通じてその直交極因子を抽出することが含まれる。
   • このアルゴリズムは、各ステップで目的関数が単調に増加することを保証する。
   • ブロック回転に起因する解の非一意性に対しては、行列の成分ごとの収束ではなく、KKT 条件の収束に焦点を当てることで対処する。
3. LOCG 加速（アルゴリズム 3.2）： 効率を向上させるため、著者らは局所最適共役勾配（LOCG）加速を導入する。この手法は、現在の反復点、直前の反復点、および残差（勾配）によって張られる探索部分空間を構築する。その後、最適化はこの縮小された部分空間内で実行され、必要な外側反復回数が大幅に削減される。

収束解析
本論文は、標準アルゴリズムおよび加速アルゴリズムの両方に対して厳密な収束解析を提供する：

• 単調性： 目的関数はすべての反復で単調に増加することが証明される。
• 大域収束： 特定の条件下（例えば、集積点が孤立しており、関連する勾配行列がフルランクである場合など）において、反復点の列が大域的に停留点に収束することが示される。
• KKT 充足： 列自体の大域収束がなくても、計算された反復点が KKT 条件を次第に満たすことが証明される。具体的には、勾配行列の最小特異値がゼロから離れて有界である限り、極分解条件の残差はゼロに収束する。
• 一般化： 収束証明は目的関数および勾配の一般的な性質に依存しており、結果は PTBD だけでなく、より広範なクラスの問題にも適用可能であることを示唆している。

数値結果
ランダムに生成された、サイズが異なる（最大 $600 \times 550 \times 600$）実数および複素数テンソルに対して、広範な数値実験が行われた。

• 収束挙動： 両アルゴリズムとも、KKT 残差を約 $10^{-9}$ 以下に成功裏に低減した。入力テンソルが完全なブロック対角化可能に近づくにつれて（ノイズパラメータ $\eta$ によって制御される）、必要な反復回数は減少した。
• 効率性： LOCG 加速版（accNPDo）は、標準的な NPDo（ガウス・ザイデル）手法と比較して、外側反復回数が劇的に減少することを示した。
• スケーラビリティ： CPU 時間はテンソルサイズパラメータに対して線形に増加することが観察された。加速手法は、総計算時間の点で常に標準手法を上回った。
• 目的関数の軌跡： KKT 残差は厳密に単調ではないが、目的関数の値は単調に増加する。著者らは、KKT 残差に、目的関数値のジャンプに対応する一時的なスパイクが観察され、アルゴリズムが局所的な「鞍点」を脱出してより良い停留点に到達していることを示唆していると報告した。

意義と主張
本論文は、NPDo 手法が、PT-SVD や Tucker 分解を特殊な場合として包含する、支配的なテンソルブロック対角化の計算のための統合フレームワークを提供すると主張する。

• 理論的貢献： 主要な理論的貢献は、この特定の結合された極分解問題のクラスに適用される交互 SCF 法に対する大域収束の確立である。著者らは、以前の研究（テンソル SVD や Tucker 分解に関するものなど）が同様の KKT 条件を確立していた一方で、本論文は収束速度に関する定量的結果や KKT 残差の挙動を含む、より包括的な収束解析を提供していると指摘する。
• 実用的有用性： 提案された手法は、高次元データからブロック対角構造を抽出するための効率的でスケーラブルなアルゴリズムを提供し、LOCG 加速により大規模問題への適用を可能にする。
• 一般性： この手法は複素テンソルに対して定式化されており、自動的に実数テンソルにも適用され、収束理論はシュティフェル多様体上の結合された極分解を含む他の最適化問題への適用可能性を示唆する形で提示されている。