低階数最良近似行列を用いた非負行列因子逐次分解法に関する一考察

摘要

Given a non-negative matrix, the non-negative matrix factorization (NMF) is a problem to find a pair of smaller non-negative matrices, say factor matrices, of which multiplication well approximates the original matrix. The NMF attracts great attention because it is useful to obtain a compact representation of non-negative data. A most well-known method named "multiplicative update" was proposed by Lee and Seung. This method is designed to reduce monotonically the Frobenius norm of the approximation error, which unfortunately can not often reach a good approximation due to the nonconvexity of the cost function of a pair of matrices. In this report, we propose a pair of efficient algorithms for the NMF by introducing a reasonable search domain for candidates of each factor matrix. The proposed search domain for the left (right) factor matrix is defined as all nonnegative matrices of which column (row) space is restricted in the column (row) space of the reduced rank best approximation matrix of the original matrix, where the reduced rank best approximation matrix is obtained as the truncated singular value decomposition. Finally, by comparing with the multiplicative update, we verified that the proposed algorithms exhibit much better convergence performance.%与えられた非負行列をサイズの小きな2つの非負行列（左因子行列と右因子行列）の横に近似分解する問題を非負行列因子分解（Nonnegative Matrix Factorization）といい，非負信号のブラインド信号源分離を実現するための基盤として脳信号処理や画像の特徴抽出の分野で注目きれている．LeeとSeungは，フロペニウスノルムを近似誤差の評価尺度として定義し，この尺度を各因子について交互に単調減少させるアルゴリズム「乗算型更新法:multiplicative update」を提案している．乗算型更新法は，現在，最も強力なアルゴリズムの1つとして知られているが，評価関数の非凸性からよい近似解にしばしば到達しない．小文では，収束性能のよい2つの非負行列因子分解アルゴリズムを提案している．2つのアルゴリズムは，ともに与えられた非負行列の特異値分解を利用することにより，左因子行列（右因子行列）の列空間（行空間）を，低階数最良近似行列の列空間（行空間）に絞り込む方針をとっており，探索範囲を限定することにより，局所最適解への陥りにくさを実現している．最後に数値例によって提案する2つのアルゴリズムが，乗算型更新法に比べて格段に優れた収束特性を示すことを確認している．