Near-separable Non-negative Matrix Factorization with $\ell_1$- and Bregman Loss Functions

2013-12-27 · Abhishek Kumar, Vikas Sindhwani

Recently, a family of tractable NMF algorithms have been proposed under the assumption that the data matrix satisfies a separability condition Donoho & Stodden (2003); Arora et al. (2012). Geometrically, this condition reformulates the NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. In this paper, we develop several extensions of the conical hull procedures of Kumar et al. (2013) for robust ($\ell_1$) approximations and Bregman divergences. Our methods inherit all the advantages of Kumar et al. (2013) including scalability and noise-tolerance. We show that on foreground-background separation problems in computer vision, robust near-separable NMFs match the performance of Robust PCA, considered state of the art on these problems, with an order of magnitude faster training time. We also demonstrate applications in exemplar selection settings.

📄 PDF Abstract BibTeX arXiv:1312.7167

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

PCA Principle Components Analysis (PCA) is an unsupervised method primary used for dimensionality reduction within machine learning. PCA is calculated via a singular value…

Block Alternating Bregman Majorization Minimization with Extrapolation

2021-07-09 · Le Thi Khanh Hien, Duy Nhat Phan, Nicolas Gillis, Masoud Ahookhosh 외

In this paper, we consider a class of nonsmooth nonconvex optimization problems whose objective is the sum of a block relative smooth function and a proper and lower semicontinuous block separable function. Although the …

Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization

2013-10-08 · Nicolas Gillis, Stephen A. Vavasis

Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyp…

Document Classification Hyperspectral Unmixing Single Particle Analysis

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

2026-06-26 · Shuang Li, Zhihui Zhu, Qiuwei Li arxiv

We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregma…

Distributed Optimization

Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices

2014-02-27 · NeurIPS 2014 12 · Austin R. Benson, Jason D. Lee, Bartek Rajwa, David F. Gleich

Numerous algorithms are used for nonnegative matrix factorization under the assumption that the matrix is nearly separable. In this paper, we show how to make these algorithms efficient for data matrices that have many m…

Generalized Separable Nonnegative Matrix Factorization

2019-05-30 · Junjun Pan, Nicolas Gillis

Nonnegative matrix factorization (NMF) is a linear dimensionality technique for nonnegative data with applications such as image analysis, text mining, audio source separation and hyperspectral unmixing. Given a data mat…

Audio Source Separation Hyperspectral Unmixing