Robust Non-negative Matrix Factorization under Separability Assumption

Authors : A. Kumar (IBM T.J. Watson Research Center, USA), V. Sindhwani (Google Research, NY, USA)

[Project Page][Publications]

Chapter Description

The starting point in this chapter is the family of conical hull finding procedures called Xray introduced for near-separable NMF problems with Frobenius norm loss. Xray finds anchor columns one after the other, incrementally expanding the cone and using exterior columns to locate the next anchor. Xray has several appealing features:

• it requires no more than r iterations each of which is parallelizable,
• it empirically demonstrates noise-tolerance,
• it admits efficient model selection,
• it does not require normalizations or preprocessing needed in other methods.

However, in the presence of outliers or different noise characteristics, the use of Frobenius norm approximations is not optimal. In fact, none of the existing near-separable NMF algorithms works with l₁ and Bregman loss functions. On the other hand, there exist local search based NMF algorithms for l₁ loss and Bregman divergences. In this chapter, we fill this gap and extend Xray to provide robust factorizations with respect to l_- loss, and approximations with respect to the family of Bregman divergences.