Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications

• URL: http://arxiv.org/abs/2209.12638v2
• Date: Fri, 31 Mar 2023 06:59:28 GMT
• Title: Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications
• Abstract summary: 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$.
• Score: 20.836492835594843
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a new low-rank matrix factorization model dubbed bounded simplex-structured matrix factorization (BSSMF). Given an input matrix $X$ and a factorization rank $r$, BSSMF looks for a matrix $W$ with $r$ columns and a matrix $H$ with $r$ rows such that $X \approx WH$ where the entries in each column of $W$ are bounded, that is, they belong to given intervals, and the columns of $H$ belong to the probability simplex, that is, $H$ is column stochastic. BSSMF generalizes nonnegative matrix factorization (NMF), and simplex-structured matrix factorization (SSMF). BSSMF is particularly well suited when the entries of the input matrix $X$ belong to a given interval; for example when the rows of $X$ represent images, or $X$ is a rating matrix such as in the Netflix and MovieLens datasets where the entries of $X$ belong to the interval $[1,5]$. The simplex-structured matrix $H$ not only leads to an easily understandable decomposition providing a soft clustering of the columns of $X$, but implies that the entries of each column of $WH$ belong to the same intervals as the columns of $W$. In this paper, we first propose a fast algorithm for BSSMF, even in the presence of missing data in $X$. Then we provide identifiability conditions for BSSMF, that is, we provide conditions under which BSSMF admits a unique decomposition, up to trivial ambiguities. Finally, we illustrate the effectiveness of BSSMF on two applications: extraction of features in a set of images, and the matrix completion problem for recommender systems.

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)
• One-Sided Matrix Completion from Ultra-Sparse Samples [18.28432289831719]
  We propose an unbiased estimator that normalizes each nonzero entry of the second moment by its observed frequency.<n>We show that the estimator is unbiased for any $p$ and enjoys low variance.<n>Experiments on both synthetic and real-world data validate our approach.
  arXiv  Detail & Related papers  (2026-01-18T01:33:48Z)
• Matrix Completion in Group Testing: Bounds and Simulations [2.721477719641864]
  The goal of group testing is to identify a small number of defective items within a large population.<n>In this work, we address the case where some entries of $mM$ are missing, yielding a missing measurement matrix $mG$.<n>Our aim is to reconstruct $mM$ from $mG$ using available samples and their outcome vectors.
  arXiv  Detail & Related papers  (2025-01-23T15:58:30Z)
• 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)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Likelihood estimation of sparse topic distributions in topic models and its applications to Wasserstein document distance calculations [3.679981089267181]
  In topic models, the $ptimes n$ expected word frequency matrix is assumed to be factorized as a $ptimes K$ word-topic matrix $A$. columns of $A$ are viewed as $p$-dimensional mixture components that are common to all documents. When $A$ is unknown, we estimate $T$ by optimizing the likelihood function corresponding to a plug in, generic, estimator $hatA$ of $A$.
  arXiv  Detail & Related papers  (2021-07-12T22:22:32Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Multiplicative Updates for NMF with $\eta$-Divergences under Disjoint Equality Constraints [17.49766938060264]
  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.
  arXiv  Detail & Related papers  (2020-10-30T12:31:35Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $nOmega(1)$ number of columns. We show that under certain minimal and realistic distributional settings, it is possible to obtain a $(k/epsilon)$-approximation with a nearly linear running time and poly$(k/epsilon)+O(klog n)$ columns. This is the first algorithm of any kind for achieving a $(k/epsilon)$-approximation for entrywise
  arXiv  Detail & Related papers  (2020-04-16T22:57:06Z)
• Optimal estimation of sparse topic models [3.308743964406688]
  This paper studies the estimation of $A$ that is possibly element-wise sparse, and the number of topics $K$ is unknown. We derive a new minimax lower bound for the estimation of such $A$ and propose a new computationally efficient algorithm for its recovery. Our estimate adapts to the unknown sparsity of $A$ and our analysis is valid for any finite $n$, $p$, $K$ and document lengths.
  arXiv  Detail & Related papers  (2020-01-22T03:19:50Z)

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.