Sum-of-norms regularized Nonnegative Matrix Factorization

• URL: http://arxiv.org/abs/2407.00706v1
• Date: Sun, 30 Jun 2024 14:16:27 GMT
• Title: Sum-of-norms regularized Nonnegative Matrix Factorization
• Authors: Andersen Ang, Waqas Bin Hamed, Hans De Sterck,
• Abstract summary: In this work, we propose an approximation method to estimate such rank while solving nonnegative matrix factorization (NMF) We use sum-of-norm (SON), a group-lasso structure that encourages pairwise similarity, to reduce the rank of a factor matrix where the rank is overestimated. SON-NMF is able to automatically estimate the rank from data, can deal with rank-deficient data matrix, can detect weak component with small energy.
• Score: 1.5484595752241124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When applying nonnegative matrix factorization (NMF), generally the rank parameter is unknown. Such rank in NMF, called the nonnegative rank, is usually estimated heuristically since computing the exact value of it is NP-hard. In this work, we propose an approximation method to estimate such rank while solving NMF on-the-fly. We use sum-of-norm (SON), a group-lasso structure that encourages pairwise similarity, to reduce the rank of a factor matrix where the rank is overestimated at the beginning. On various datasets, SON-NMF is able to reveal the correct nonnegative rank of the data without any prior knowledge nor tuning. SON-NMF is a nonconvx nonsmmoth non-separable non-proximable problem, solving it is nontrivial. First, as rank estimation in NMF is NP-hard, the proposed approach does not enjoy a lower computational complexity. Using a graph-theoretic argument, we prove that the complexity of the SON-NMF is almost irreducible. Second, the per-iteration cost of any algorithm solving SON-NMF is possibly high, which motivated us to propose a first-order BCD algorithm to approximately solve SON-NMF with a low per-iteration cost, in which we do so by the proximal average operator. Lastly, we propose a simple greedy method for post-processing. SON-NMF exhibits favourable features for applications. Beside the ability to automatically estimate the rank from data, SON-NMF can deal with rank-deficient data matrix, can detect weak component with small energy. Furthermore, on the application of hyperspectral imaging, SON-NMF handle the issue of spectral variability naturally.

Related papers

• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) is considered an optimal solution for adversarial multi-armed bandit (MAB) problems. We propose a new version of INF called the Implicitly Normalized Forecaster with clipping (INFclip) for MAB problems with heavy-tailed settings. We demonstrate that INFclip is optimal for linear heavy-tailed MAB problems and works well for non-linear ones.
  arXiv  Detail & Related papers  (2023-05-11T12:00:43Z)
• SymNMF-Net for The Symmetric NMF Problem [62.44067422984995]
  We propose a neural network called SymNMF-Net for the Symmetric NMF problem. We show that the inference of each block corresponds to a single iteration of the optimization. Empirical results on real-world datasets demonstrate the superiority of our SymNMF-Net.
  arXiv  Detail & Related papers  (2022-05-26T08:17:39Z)
• 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)
• Fast Rank-1 NMF for Missing Data with KL Divergence [8.020742121274417]
  A1GM minimizes the KL divergence from an input matrix to the reconstructed rank-1 matrix. We show that A1GM is more efficient than a gradient method with competitive reconstruction errors.
  arXiv  Detail & Related papers  (2021-10-25T02:05:35Z)
• Entropy Minimizing Matrix Factorization [102.26446204624885]
  Nonnegative Matrix Factorization (NMF) is a widely-used data analysis technique, and has yielded impressive results in many real-world tasks. In this study, an Entropy Minimizing Matrix Factorization framework (EMMF) is developed to tackle the above problem. Considering that the outliers are usually much less than the normal samples, a new entropy loss function is established for matrix factorization.
  arXiv  Detail & Related papers  (2021-03-24T21:08:43Z)
• 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)
• Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence [20.671178429005973]
  Kullback-Leibler (KL) divergence is one of the most widely used objective function for nonnegative matrix factorization (NMF) We propose three new algorithms that guarantee the non-increasingness of the objective function. We conduct extensive numerical experiments to provide a comprehensive picture of the performances of the KL NMF algorithms.
  arXiv  Detail & Related papers  (2020-10-05T11:51:39Z)
• Sparse Separable Nonnegative Matrix Factorization [22.679160149512377]
  We propose a new variant of nonnegative matrix factorization (NMF) Separability requires that the columns of the first NMF factor are equal to columns of the input matrix, while sparsity requires that the columns of the second NMF factor are sparse. We prove that, in noiseless settings and under mild assumptions, our algorithm recovers the true underlying sources.
  arXiv  Detail & Related papers  (2020-06-13T03:52:29Z)
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently [18.89597524771988]
  Non-negative matrix factorization (NMF) is a fundamental non-modification optimization problem with numerous applications in Machine Learning. This paper defines a multiplicative weight update type dynamics (Seung algorithm) that runs concurrently and provably avoids saddle points. An important advantage is the use concurrent implementations in parallel computing environments.
  arXiv  Detail & Related papers  (2020-02-26T06:40:23Z)

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.