低ランク行列補完は、協調フィルタリング応用において基本的な役割を果たしており、その核心的なアイデアは、変数が環境空間よりも小さい部分空間に存在することにある。多くの場合、変数に関する追加情報が既に知られており、その情報を組み込むことで予測精度が向上するという仮定は妥当である。本研究では、変数間の対間関係がグラフとして与えられている状況下における行列補完問題に着目し、それを効率的な共役勾配に基づく逐次最小化法によって定式化・導出する。この手法は、5500万を超える観測値を含む最適化問題を、最先端（確率的）勾配降下法と比較して最大2桁の速度向上で解くことが可能である。理論的にも、本手法が重み付きノルム核の一般化であることを示し、統計的一貫性の保証を導出している。実データおよび合成データを用いた実験により、本手法の有効性を検証した。