Gap-Aware Exact Nonnegative Matrix Factorization: A Two-Sided SVD Gauge and a Three-Regime W-Rank Taxonomy

技術要約：ギャップを考慮した厳密非負行列分解

問題提起
本論文は、「ギャップ・レジーム（gap regime）」における厳密非負行列分解（Exact NMF）の課題に取り組んでいる。ここで、目標となる非負ランク $r_+$ は、行列のランク $r$ を厳密に上回る（$r_+ > r$）。先行研究 [1] は、ユニフォーム・サポート・レジーム（$r_+ = r$）における「コーン・レイ（cone-ray）」パイプラインを確立したが、このアプローチには制約がある。すなわち、内積次元が行列のランクと一致することを前提としており、復元される因子 $W$ のランクを $r$ に制限しており、さらに特異値分解（SVD）のゲージ（gauge）における自由度が欠如している。著者らは、このパイプラインを $r_+ > r$ のケースへと拡張することを目指している。この場合、解空間の幾何学的構造が大きく変化する。また、因子 $W$ のランク構造に基づいた、復元可能な分解の分類も試みている。

手法
核となる貢献は、コーン・レイ・パイプラインを一般化した両側SVDゲージ・フレームワークである。

1. 対称パラメトリゼーション（Symmetric Parametrization）: ランク $r$ の切断SVD因子 $U_r$ および $V_r$ を使用する代わりに、本手法では拡張された直交フレームを構築する：
   $$U_{r_+}(G) = [U_r \mid U_\perp G], \quad V_{r_+}(K) = [V_r \mid V_\perp K]$$
   ここで、$U_\perp$ と $V_\perp$ は $M$ の列空間および行空間の直交補空間をスパンし、$(G, K)$ はスティフェル多様体 $St(m-r, r_+-r) \times St(n-r, r_+-r)$ 上の行列である。
2. 平方一貫性（Square Consistency）: 分解の制約 $WH = M$を、中間因子$Q$および$P$ に関する平方一貫条件へと変換する：
   $$QP = \text{diag}(S_r, 0) \in \mathbb{R}^{r_+ \times r_+}$$
   これにより、$Q$ と $P$ のランクは、その積のランクが $r$ である限り、独立して $r$ から $r_+$ の範囲で変動することが可能となる。
3. アルゴリズム・パイプライン: 本手法は、二段階のアプローチを採用している：
   • フェーズA（SVD-ゲージ・コーン・レイ）: 固定されたゲージ $(G, K)$ に対して、二重記述法（Double Description Method; DDM）を用いて、$U_{r_+}(G)$ および $V_{r_+}(K)$ によって定義される錐（cone）の極端なレイ（extreme rays）を計算する。レイのサブセットを「鈍角性（obtuseness）」によってランク付けし、閉形式のウィットネス（witness）の探索を試みる。これが失敗した場合は、交互線形計画法（alt-LP）へとフォールバックする。
   • フェーズB（ランク欠損 $W$ ブランチ）: $M$ の列の $r_+$ 個のサブセットを直接列挙する補完的なブランチである。線形計画法（LP）を用いて、列ごとに実行可能性をテストする。このブランチは、$W$ が $M$ の列のサブセットである場合（これは $\text{rank}(W) = r$ を意味する）の解を対象としている。

三つのレジームによる分類学
本論文は、因子 $W$ のランクに基づき、厳密NMF問題を以下の三つのレジームに分類している：

• レジームA ($\text{rank}(W) = r_+$): フル列ランク。データ錐の余次元は、外側の錐に対して $r_+ - r$ となる。著者らは、高密度なランダム行列において、「スラック包囲（slack enclosure）」現象（追加の次元が寛大なスラックを提供する）と、有効な非負ランク分解（NRF）多様体の「厚み」により、盲目的なSVDによる $(G, K)$ の選択が確率1で成功することを示している。
• レジームB ($\text{rank}(W) = r$): $W$ は $M$ の列のサブセットである。ここでは、有効なNRF多様体は、構造的制約（例：ブロック対角行列）により、測度ゼロの集合（多くの場合、グラスマン多様体における単一点）へと退化する。盲目的なSVDはほぼ確実に失敗し、一様スティフェル・サンプリングでも救済できない。しかし、ランク欠損 $W$ ブランチ（フェーズB）は、これらのケースを効率的に解決する。
• レジームC ($r < \text{rank}(W) < r_+$): $W$ は列のサブセットではなく、そのランクは $r$ と $r_+$ の間にある。正八角形のスラック行列が主要な例である。対称的な定式化はこのような解を表現可能であるが（オラクル・ゲージにより検証済み）、盲目的な $(G, K)$ の探索は未解決のままである。損失関数は組合せ論的なセル上で区分的に定数（piecewise constant）であり、そのため局所リーマン最適化手法（勾配降下法、共役勾配法）は停滞を引き起こす。

主な結果

• 高密度行列（レジームA）: $r=4, r_+ \in \{5, 6\}$ の $10 \times 10$ 高密度ランダム・ギャップ行列において、本パイプラインは閉形式のウィットネス・フェーズのみを用いて100/100の復元率を達成した。これは、$r_+ = r$ の場合（79〜87/100で飽和）を上回っており、これはギャップが提供する幾何学的な「スラック」に起因するとされている。
• 構造化行列（レジームB）: $M_k = \text{diag}(C, J_k)$ という家族（$C$ はランク4の巡回行列、$J_k$ は全成分1の行列）において、盲目的なSVDパイプラインは $k \ge 2$ で完全に失敗する（成功 0/4）。一様スティフェル再始動も失敗する（ヒット 0/50）。しかし、ランク欠損 $W$ ブランチは、ミリ秒単位で4/4の成功を回復させる。
• 正八角形（レジームC）: 正八角形のスラック行列（$r=3, r_+=6$）について、サイズ6のNRFが存在し、標準的なNMFソルバー（sklearn）によって高い精度で発見される。しかし、提案されたツールキットはこれを盲目的に見つけることができない。オラクル実験により、本定式化は解を表現する能力があることが確認されているが、盲目的な探索（スティフェル/グラスマン多様体サンプリングおよびリーマン勾配降下法）は、残差がゼロから遠い局所解に陥り、適切なゲージを見つけることができなかった。
• 統合ツールキット: フェーズBを実行した後にフェーズAを実行するオーケストレーターは、高密度な描画における退行なしに、レジームAとレジームBの両方をカバーし、テストされたこれら両レジームの連合に対して100%の成功を達成している。

意義と主張
本論文は、厳密NMFのパイプラインをギャップ・レジームへと拡張し、統一的な幾何学的フレームワークを提供することを主張している。その意義は以下の点にある：

1. 幾何学的洞察: ギャップ・レジーム（$r_+ > r$）が、高密度行列における包囲問題を緩和し、盲目的なSVDの選択を効果的にすることを示す一方で、タイトなランク制約を持つ構造化行列が、盲目的なヒューリスティックでは捉えられない測度ゼロの解空間を生み出すことを明らかにしている。
2. 実用的な堅牢性: 構造化行列に対するゲージ問題を回避する「ランク欠損 $W$」ブランチを導入することで、高密度ランダムデータと特定の構造化ファミリー（ブロック対角和など）の両方で動作するツールキットを実現している。
3. 限界と未解決問題: 著者らは、レジームCが依然として未解決であることを謙虚に認めている。正八角形における局所最適化手法の失敗は、根本的な病理を示している。すなわち、損失関数は組合せ論的なセル上で区分的に定数であり、勾配ベースの手法がセルの壁を越えることを妨げている。著者らは、より滑らかな代理損失（surrogate losses）やベイシン・ホッピング戦略の必要性を将来の課題として挙げており、レジームCの盲目的な探索を解決したとは主張していない。

本研究は、「両側SVDゲージ」および「三つのレジームによる分類学」として提示されており、厳密NMFツールのカバー範囲を明確にし、盲目的なSVDが十分なケース、列のサブセット列挙が必要なケース、そして問題が未解決のまま残るケースを区別している。