Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization

Arnaud Vandaele, Nicolas Gillis, Qi Lei, Kai Zhong, Inderjit Dhillon

Research output: Contribution to journalArticlepeer-review

Abstract

Given a symmetric nonnegative matrix A, symmetric nonnegative matrix factorization (symNMF) is the problem of finding a nonnegative matrix H, usually with much fewer columns than A, such that A ≈ HHT. SymNMF can be used for data analysis and in particular for various clustering tasks. Unlike standard NMF, which is traditionally solved by a series of quadratic (convex) subproblems, we propose to solve symNMF by directly solving the nonconvex problem, namely, minimize A-HHT2, which is a fourth-order nonconvex problem. In this paper, we propose simple and very efficient coordinate descent schemes, which solve a series of fourth-order univariate subproblems exactly. We also derive convergence guarantees for our methods and show that they perform favorably compared to recent state-of-the-art methods on synthetic and real-world datasets, especially on large and sparse input matrices.

Original languageEnglish (US)
Article number7513400
Pages (from-to)5571-5584
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume64
Issue number21
DOIs
StatePublished - Nov 1 2016

Keywords

  • Symmetric nonnegative matrix factorization
  • completely positive matrices
  • coordinate descent

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization'. Together they form a unique fingerprint.

Cite this