Exact Nonnegative Matrix Factorization via Cone-Ray Witnesses: Obtuseness Ranking, Saturation Curves, and an Augmented Alt-LP Breakthrough

技術要約：錐状レイ・ウィットネス（Cone-Ray Witnesses）による厳密な非負行列因子分解

問題提起
本論文は、**厳密な非負行列因子分解（Exact Nonnegative Matrix Factorization: NMF）**の問題を扱う。非負ランクが最大 $r$ である非負行列 $A \in \mathbb{R}^{m \times n}_{\ge 0}$ が与えられたとき、目標は $A = WH^\top$ かつ残差ゼロを満たす非負因子 $W \in \mathbb{R}^{m \times r}_{\ge 0}$ および $H \in \mathbb{R}^{n \times r}_{\ge 0}$ を見つけることである。トピックモデリングや推薦システムで使用される近似NMF（低誤差の近似を求めるもの）とは異なり、本研究は、**分離可能性（separability）**条件（$A$ の列が基底ベクトルの部分集合であるという条件）を仮定せずに、厳密な因子分解を回収することに焦点を当てている。本論文は、理論的には厳密な回復が可能であるが、組合せ論的な制約により計算が困難となる小規模なインスタンスを対象としている。

手法
著者らは、NMF問題を多面体錐（polyhedral cones）上の探索へと変換する「錐状レイ・パイプライン（cone-ray pipeline）」を提案している。その手法は以下の4つのステージで進行する：

1. SVD（特異値分解）による次元削減: 入力行列 $A$ は、薄いSVD（$A = U S V^\top$）によって分解される。著者らは、直交基底 $A_{orth} = U_{:,1:r} \sqrt{S_{1:r,1:r}}$ および $A_{orth1} = V_{:,1:r} \sqrt{S_{1:r,1:r}}$ を定義する。いかなる厳密な因子分解も、$W = A_{orth}Q$ および $H = A_{orth1}P$（ただし $Q, P \in \mathbb{R}^{r \times r}$ は $QP^\top = I_r$ を満たす）として表現できる。
2. 多面体錐の構成: $W$ と $H$ の非負制約は、$Q$ と $P$ の列が $A_{orth}$ および $A_{orth1}$ によって定義される特定の多面体錐内に存在しなければならないことを意味する。著者らは、極レイ（extreme rays） $R_{orth}$ および $R_{orth1}$ を計算するために、cddlib を用いた**二重記述法（Double Description Method: DDM）**を使用する。
3. 一様サポート・ウィットネス（閉形式）: コアとなる革新は、パラメータ化において $Q$ と $P$ の列が、錐の極レイの特定の $r$ 個のサブセットからの非負結合体に制限される点である。$T$ および $K$ をレイのインデックスの $r$ 個のサブセットとする。もし $Q = R_T \mu$ かつ $P = R_K \nu$ であり、$\nu = I_r$ であるならば、制約 $QP^\top = I_r$ は以下の閉形式の条件へと収束する：
   $$M_T = R_T^{-1} (R_K^\top)^{-1} \ge 0$$
   もし行列 $M_T$ が要素ごとに非負であれば、即座に厳密なNMFが回収される。このテストは計算コストが極めて低い（マイクロ秒単位）。
4. 鈍角度に基づいた探索（Obtuseness-Ranked Search）: $r$ 個のサブセットの数は組合せ爆発するため、著者らは候補となるサブセットを幾何学的な「鈍角度（obtuseness）」スコア $|\det(R_T)| / \prod \|R_{T,i}\|$ によってランク付けする。このスコアはレイの近直交性を測定しており、高いスコアは「太い」錐であることを示し、非負のウィットネスが得られる可能性が高いことを示す。アルゴリズムは、このランキングの上位候補を順に探索する。
5. 拡張型交互線形計画法（Augmented Alt-LP）によるフォールバック: 閉形式のウィットネス $M_T$ が実行不可能（すなわち負の要素を含む）な場合、手法は単にそのペアを破棄するのではなく、既存のレイから角度的に最大限離れた $k=2$ 個の追加のレイを加えて、サポート集合 $T$ と $K$ を拡張する。これにより、$r \times (r+k)$ のサポートが作成される。その後、著者らは、厳密な一様サポート制約を緩和しつつ計算可能性を維持しながら、スラックを最小化するように係数 $\mu, \nu$ を求めるために**交互線形計画法（alternating linear program: alt-LP）**を用いて解を求める。

主な貢献

1. 一様サポート下での閉形式ウィットネス: 本論文は、厳密ランクの入力に対して、結合非負制約が事前計算された行列 $M_T$ の単純な要素ごとの非負チェックに減少することを確立した。これにより、厳密な因子分解の実現可能性を確認するためのマイクロ秒単位のテストが可能となった。
2. 鈍角度ランク探索と飽和分析: $m=n=10$ の100回のモンテカルロ試行を通じて、著者らは鈍角度ヒューリスティックの性能を特性化した。彼らは、探索が上位200個の候補という予算で飽和することを示した。つまり、予算を上位400個に増やしても、得られる利得は無視できるほど小さい。決定的なのは、この時点での失敗は、探索予算の不足ではなく、構造的な問題（錐が近直交なサブセットを欠いていること）に起因することを示した点である。
3. スケーリングの壁の特定: 論文では以下の具体的な失敗モードを記録している：
   • 次元数: 固定された $r$ に対して $m, n$ を増加させると（例：$m=n=15$）、デュアル錐が「細く」なり、近直交なサブセットが欠如するため、成功率が実際に低下する。
   • DDMのボトルネック: Olivetti faces（$400 \times 4096$）のような大規模データセットでは、小さな $r$ であっても不等式の爆発によりDDMステップが実行不能になる。
4. ハイブリッド拡張型Alt-LPによる突破口: 主要な貢献は、閉形式のテストと拡張サポートAlt-LPを組み合わせたハイブリッドアルゴリズムである。必要に応じてのみ一様サポートの制限を解除することで、この手法は閉形式のウィットネスで見られた構造的な天井を打破する。

結果

• 小規模スケール ($m=n=10$):
  • 閉形式（上位200）のアプローチによる成功率は、$r=4, 5, 6$ に対して100試行中 79/85/58 であった。
  • ハイブリッドアプローチ（閉形式 + 拡張Alt-LP）は、これらを 99/95/75 に改善し、事実上、構造的な天井を打破した。
  • 成功した場合、再構成誤差はマシン精度（$\sim 10^{-15}$）であった。
• 中規模スケール ($m=n=15$):
  • 閉形式のアプローチは大幅に失敗した（$r=4, 5, 6$ に対して 37/7/0）。
  • ハイブリッドアプローチは 78/28/0 の成功を回収し、改善は見られたものの、$r=6$ においては錐が細すぎて $k=2$ の拡張でも対応できないという新たな構造的壁に突き当たった。
• 大規模スケール (Olivetti):
  • パイプラインはDDMステップを1時間の予算内で完了できず、高次元データにおける極限値の列挙の困難さを浮き彫りにした。

意義と主張
本論文は、分離可能性の仮定に依存しない、厳密なNMFのための完全に実行可能なツールキットを提供すると主張している。その意義は以下の通りである：

• 証明（Certification）: 近似手法とは異なり、このツールキットは成功した際に、厳密性の証明（マシン精度での再構成）を返す。
• 幾何学的洞察: 厳密な因子分解に必要とされる幾何学的条件（錐のレイの近直交性）を厳密に特性化し、「太い」錐が閉形式の解に必要であることを示した。
• 実用的な突破口: ハイブリッドな拡張Alt-LP法は、閉形式のウィットネスで見られた構造的な天井を決定的に打破し、小規模次元において成功率を90%以上に押し上げた最初のバリアントである。

著者らは限界についても謙虚であり、パイプラインが4つの「スケーリングの壁」に直面していることを認めている：DDMのレイ数の爆発、一様サポートの制限（一部緩和済み）、数値的コンディション、および完全な非一様バリアントにおけるスラックLPのプラトーである。彼らは、今後の研究がサンプリングによるDDMのスケーラビリティ、あるいは残りの構造的失敗に対するより深い拡張や代替ソルバー（NNLS）に対処する必要があることを示唆している。