担当 : 相島 健助
題目 : 低ランク行列補完アルゴリズムについて
概要 :
線形制約のもとで行列のランクを最小化する問題は，レコメンダシステムのような機会学習的，統計的な数理モデルを多く含んでおり近年盛んに研究されている．この最適化問題は一般にNP困難であり，様々な近似解法が提案されているが，それらは何らかの意味で特異値分解に基づくものが多い．
文献[2]では，特異値分解に基づく単純な解法とグラスマン多様体上の勾配法[1]との関係に着目し，ある種の交互最小二乗法[3]と同値になるように計量を定義することで，解の探索方向をスケーリングされた勾配方向にとる解法を提唱している．さらにこの計量に基づき新たに共役勾配法を提案し，その優れた性能を報告している．本発表では文献[2]におけるアルゴリズム的な議論を中心に説明する．
参考文献
[1] R. H. Keshavan, S. Oh, and A. Montanari. Matrix completion from a few entries, IEEE Trans. Inform. Theory 56 (2010), 6, pp. 2980–2998.
[2] T. Ngo and Y. Saad, Scaled gradients on Grassmann manifolds for matrix completion, in Advances in Neural Information Processing Systems 25, NIPS, 2012, pp. 1421–1429. (Spotlight), paper available in http://books.nips.cc/nips25.html.
[3] Z. Wen, W. Yin, and Y. Zhang. Solving a low-rank factorization model for matrix completion using a non-linear successive over-relaxation algorithm, Math. Prog. Comp. (2012) 4, pp. 333–361
