Nonnegative matrix factorization with gradient vertex pursuit

Nonnegative Matrix Factorization (NMF), defined as factorizing a nonnegative matrix into two nonnegative factor matrices, is a particularly important problem in machine learning. Unfortunately, it is also ill-posed and NP-hard. We propose a fast, robust, and provably correct algorithm, namely Gradie...

Full description

Saved in:
Bibliographic Details
Main Authors: Tran, Dung N., Tao Xiong, Chin, Sang Peter, Tran, Trac D.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Gradient Vertex Pursuit
greedy pursuit
Hyperspectral imaging
Machine learning
nonnegative matrix factorization
Optimization
Pursuit algorithms
Robustness
Signal processing algorithms
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Nonnegative Matrix Factorization (NMF), defined as factorizing a nonnegative matrix into two nonnegative factor matrices, is a particularly important problem in machine learning. Unfortunately, it is also ill-posed and NP-hard. We propose a fast, robust, and provably correct algorithm, namely Gradient Vertex Pursuit (GVP), for solving a well-defined instance of the problem which results in a unique solution: there exists a polytope, whose vertices consist of a few columns of the original matrix, covering the entire set of remaining columns. Our algorithm is greedy: it detects, at each iteration, a correct vertex until the entire polytope is identified. We evaluate the proposed algorithm on both synthetic and real hyperspectral data, and show its superior performance compared with other state-of-the-art greedy pursuit algorithms.
ISSN:1520-6149
2379-190X
DOI:10.1109/ICASSP.2015.7178346