Multiplicative Updates for NMF with $\beta$-Divergences under Disjoint Equality Constraints

• URL: http://arxiv.org/abs/2010.16223v2
• Date: Thu, 28 Apr 2022 08:44:54 GMT
• Title: Multiplicative Updates for NMF with $\beta$-Divergences under Disjoint Equality Constraints
• Abstract summary: Nonnegative matrix factorization (NMF) is the problem of approximating an input nonnegative matrix, $V$, as the product of two smaller nonnegative matrices, $W$ and $H$. We introduce a general framework to design multiplicative updates (MU) for NMF based on $beta$-divergences ($beta$-NMF) with disjoint equality constraints, and with penalty terms in the objective function.
• Score: 17.49766938060264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonnegative matrix factorization (NMF) is the problem of approximating an input nonnegative matrix, $V$, as the product of two smaller nonnegative matrices, $W$ and $H$. In this paper, we introduce a general framework to design multiplicative updates (MU) for NMF based on $\beta$-divergences ($\beta$-NMF) with disjoint equality constraints, and with penalty terms in the objective function. By disjoint, we mean that each variable appears in at most one equality constraint. Our MU satisfy the set of constraints after each update of the variables during the optimization process, while guaranteeing that the objective function decreases monotonically. We showcase this framework on three NMF models, and show that it competes favorably the state of the art: (1)~$\beta$-NMF with sum-to-one constraints on the columns of $H$, (2) minimum-volume $\beta$-NMF with sum-to-one constraints on the columns of $W$, and (3) sparse $\beta$-NMF with $\ell_2$-norm constraints on the columns of $W$.

Related papers

• On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization [9.842769671181276]
  We show that entrywise power matrix factorization (EPMF) is NP-hard, already when $r=2$, the smallest non-trivial case.<n>EPMF is equivalent to the problem of flipping the signs of the entries of a given matrix $X$ to obtain a rank-$r$ matrix.
  arXiv  Detail & Related papers  (2026-07-06T09:50:20Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Maximum-Volume Nonnegative Matrix Factorization [10.219251148447668]
  MaxVol NMF is identifiable under the same conditions as MinVol NMF in the noiseless case.<n>We prove that the solutions of MaxVol NMF with the largest volume correspond to clustering the columns of $X$ in disjoint clusters.<n>We also present a normalized variant of MaxVol NMF that exhibits better performance than MinVol NMF and MaxVol NMF.
  arXiv  Detail & Related papers  (2026-02-04T17:43:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We quantify the performance of the approximation with the Monge-Kantorovich $p$-cost. We may then reform the problem as minimizing a functional $mathscrJ_p(f)$ under a constraint on the Sobolev budget.
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• On the Connection Between Non-negative Matrix Factorization and Latent Dirichlet Allocation [0.0]
  Non-negative matrix factorization with the generalized Kullback-Leibler divergence (NMF) and latent Dirichlet allocation (LDA) are two popular approaches for dimensionality reduction of non-negative data. We show that NMF with normalization constraints on the columns of both matrices of the decomposition and a Dirichlet prior on the columns of one matrix is equivalent to LDA.
  arXiv  Detail & Related papers  (2024-05-30T23:54:17Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications [20.836492835594843]
  We propose a new low-rank matrix factorization model dubbed simplex-structured matrix factorization (BSSMF) BSSMF is particularly well suited when the entries of the input matrix $X$ belong to a given interval. In this paper, we first propose a fast algorithm for BSSMF, even in the presence of missing data in $X$.
  arXiv  Detail & Related papers  (2022-09-26T12:37:37Z)
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
  We consider a twice-differentiable, $L$-smooth, $mu$-strongly convex objective $phimph over an $ntimes n$fracfrac14(L/mu-1)2rstar$. Despite non-locality, local optimization is guaranteed to globally converge from any initial point to the global optimum.
  arXiv  Detail & Related papers  (2022-07-05T03:18:17Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  Nonnegative matrix factorization (NMF) has been widely studied in recent years due to its effectiveness in representing nonnegative data with parts-based representations. We propose a new NMF method with log-norm imposed on the factor matrices to enhance the sparseness. A novel column-wisely sparse norm, named $ell_2,log$-(pseudo) norm, is proposed to enhance the robustness of the proposed method.
  arXiv  Detail & Related papers  (2022-04-22T11:38:10Z)
• Structured Sparse Non-negative Matrix Factorization with L20-Norm for scRNA-seq Data Analysis [10.628932392896374]
  We introduce a row-s NMF with $ell_2,0$-norm constraint (ONMF_$ell_20$) to enhance clustering performance. We propose an efficient algorithm to solve matrixMF_$ell_20$ by transforming it into a series of penalized datasets.
  arXiv  Detail & Related papers  (2021-04-27T13:31:41Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.