Online Nonnegative Matrix Factorization with Outliers

Abstract

We propose a unified and systematic framework for performing online nonnegative matrix factorization in the presence of outliers. Our framework is particularly suited to large-scale data. We propose two solvers based on projected gradient descent and the alternating direction method of multipliers. We prove that the sequence of objective values converges almost surely by appealing to the quasi-martingale convergence theorem. We also show the sequence of learned dictionaries converges to the set of stationary points of the expected loss function almost surely. In addition, we extend our basic problem formulation to various settings with different constraints and regularizers. We also adapt the solvers and analyses to each setting. We perform extensive experiments on both synthetic and real datasets. These experiments demonstrate the computational efficiency and efficacy of our algorithms on tasks such as (parts-based) basis learning, image denoising, shadow removal and foreground-background separation.

References in corpus (12)

• A note on the group lasso and a sparse group lasso
• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• Nonlinear hyperspectral unmixing with robust nonnegative matrix factorization
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• Non-convex Robust PCA
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Dictionary Learning over Distributed Models
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• Compressed Nonnegative Matrix Factorization is Fast and Accurate
• Heuristics for Exact Nonnegative Matrix Factorization
• Dictionary Learning for Massive Matrix Factorization
• Learning efficient sparse and low rank models

Cited by in corpus (6)

• Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumption
• Privacy-preserving Non-negative Matrix Factorization with Outliers
• Adversarially-Trained Nonnegative Matrix Factorization
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Online Nonnegative Matrix Factorization with General Divergences
• A Unified Framework for Stochastic Matrix Factorization via Variance Reduction