Nonnegative Matrix Factorization with Earth Mover's Distance metric
Roman Sandler, Michael Lindenbaum · 2009 IEEE Conference on Computer Vision and Pattern Recognition · 2009
Nonnegative Matrix Factorization (NMF) approximates a given data matrix as a product of two low rank nonnegative matrices, usually by minimizing the L2or the KL distance between the data matrix and the matrix product. This factorization was shown to be useful for several important computer vision applications. We propose here a new NMF algorithm that minimizes the Earth Mover's Distance (EMD) error between the data and the matrix product. We propose an iterative NMF algorithm (EMD NMF) and prove its convergence. The algorithm is based on linear programming. We discuss the numerical difficulties of the EMD NMF and propose an efficient approximation. Naturally, the matrices obtained with EMD NMF are different from those obtained with L2NMF. We discuss these differences in the context of two challenging computer vision tasks - texture classification and face recognition - and demonstrate the advantages of the proposed method.