スパースモデリングによる最小リンクフロー問題の一解法

摘要

近年、スパースモデリングと呼ばれる、モデルの特徴量が有するスパース性を利用することで、少数の観測値からモデルの未知の特徴量を推定する統計的手法が注目を浴びている。信号処理や画像処理の分野を中心に研究が進んでいるスパースモデリングであるが、少数ながらも情報ネットワーク分野における応用の検討も始まっている。本稿では、ネットワークフローの問題に、スパースモデリングがどのように応用できるかを検討する。ネットワークフローの問題の一つとして、フローのコストを最小化する最小コストフロー問題に類似した問題であり、フローの通過するリンク数を最小化する「最小リンクフロー問題」を考える。ネットワークの最小リンクフロー問題を、スパースモデリングによって定式化するとともに、スパースモデルによって表現したネットワークの最小リンクフロー問題を、既存の貪欲アルゴリズム（直交マッチング追跡）によってどの程度正確に解くことができるかを調査する。