Nonnegative Matrix Factorization with Earth Mover's Distance Metric for Image Analysis

Area of Science:

• Computer Science
• Machine Learning
• Data Analysis

Background:

• Nonnegative matrix factorization (NMF) is crucial for data approximation in computer vision.
• Existing NMF methods often minimize L2 or KL distances, yielding specific matrix properties.
• The limitations of current NMF distance metrics in certain applications motivate new approaches.

Purpose of the Study:

• To introduce two novel NMF algorithms that minimize Earth Mover's Distance (EMD) error.
• To explore the application of EMD-based NMF in computer vision tasks.
• To demonstrate the convergence and practical utility of the proposed EMD NMF algorithms.

Main Methods:

• Developed two iterative NMF algorithms: EMD NMF and bilateral EMD NMF.
• Utilized linear programming methods as the basis for the iterative algorithms.
• Analyzed convergence properties and addressed numerical challenges with efficient approximations.

Main Results:

• The proposed EMD NMF algorithms produce distinct matrix factorizations compared to L2-NMF.
• Demonstrated the effectiveness of EMD NMF in texture classification and face recognition benchmarks.
• Achieved the first instance of NMF-based image segmentation using the new methods.

Conclusions:

• EMD NMF offers a valuable alternative to traditional NMF methods for specific computer vision problems.
• The new algorithms show significant advantages in image segmentation, texture classification, and face recognition.
• The convergence proofs and practical approximations support the viability of EMD NMF.