Off-diagonal symmetric nonnegative matrix factorization
From MaRDI portal
Publication:820738
Abstract: Symmetric nonnegative matrix factorization (symNMF) is a variant of nonnegative matrix factorization (NMF) that allows to handle symmetric input matrices and has been shown to be particularly well suited for clustering tasks. In this paper, we present a new model, dubbed off-diagonal symNMF (ODsymNMF), that does not take into account the diagonal entries of the input matrix in the objective function. ODsymNMF has three key advantages compared to symNMF. First, ODsymNMF is theoretically much more sound as there always exists an exact factorization of size at most where is the dimension of the input matrix. Second, it makes more sense in practice as diagonal entries of the input matrix typically correspond to the similarity between an item and itself, not bringing much information. Third, it makes the optimization problem much easier to solve. In particular, it will allow us to design an algorithm based on coordinate descent that minimizes the component-wise norm between the input matrix and its approximation. We prove that this norm is much better suited for binary input matrices often encountered in practice. We also derive a coordinate descent method for the component-wise norm, and compare the two approaches with symNMF on synthetic and document data sets.
Recommendations
- Adaptive computation of the symmetric nonnegative matrix factorization (SymNMF)
- SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering
- scientific article; zbMATH DE number 7404610
- On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices
- A symmetric rank-one quasi-Newton method for nonnegative matrix factorization
Cites work
- Computing a nearest correlation matrix with factor structure
- Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization
- Coordinate descent algorithms
- Coordinate-friendly structures, algorithms and applications
- Efficient and Non-Convex Coordinate Descent for Symmetric Nonnegative Matrix Factorization
- First-order methods in optimization
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- scientific article; zbMATH DE number 1933860 (Why is no real title available?)
- Inexact Block Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
- Non-Negative Matrix Factorization Revisited: Uniqueness and Algorithm for Symmetric Decomposition
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- On the computational complexity of membership problems for the completely positive cone and its dual
- SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering
- Weighted median algorithms for \(L_ 1\) approximation
Cited in
(6)- Symmetric nonnegative matrix trifactorization
- scientific article; zbMATH DE number 4168848 (Why is no real title available?)
- Symmetry-based matrix factorization
- Coseparable Nonnegative Matrix Factorization
- On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices
- Adaptive computation of the symmetric nonnegative matrix factorization (SymNMF)
This page was built for publication: Off-diagonal symmetric nonnegative matrix factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820738)
