Nonnegative Matrix Factorization with Earth Mover's Distance metric

Nonnegative Matrix Factorization (NMF) approximates a given data matrix as a product of two low rank nonnegative matrices, usually by minimizing the L 2 or the KL distance between the data matrix and the matrix product. This factorization was shown to be useful for several important computer vision...

Full description

Saved in:
Bibliographic Details
Main Authors: Sandler, Roman, Lindenbaum, Michael
Format: Conference Proceeding
Language:English
Subjects:
Application software
Computer science
Computer vision
Earth
Face recognition
Geoscience
Image reconstruction
Iterative algorithms
Linear programming
Matrix decomposition
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Nonnegative Matrix Factorization (NMF) approximates a given data matrix as a product of two low rank nonnegative matrices, usually by minimizing the L 2 or 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 L 2 NMF. 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.
ISSN:1063-6919
DOI:10.1109/CVPR.2009.5206834