Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras

• URL: http://arxiv.org/abs/2309.13914v1
• Date: Mon, 25 Sep 2023 07:29:59 GMT
• Title: Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras
• Abstract summary: We investigate two problems involving matrix factorization over the tropical algebra. For the first problem, we propose an improved algorithm that avoids many of the local optima. The second formulation considers the approximate decomposition of a given matrix into the product of three matrices.
• Score: 27.680519297540535
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix Factorization (MF) has found numerous applications in Machine Learning and Data Mining, including collaborative filtering recommendation systems, dimensionality reduction, data visualization, and community detection. Motivated by the recent successes of tropical algebra and geometry in machine learning, we investigate two problems involving matrix factorization over the tropical algebra. For the first problem, Tropical Matrix Factorization (TMF), which has been studied already in the literature, we propose an improved algorithm that avoids many of the local optima. The second formulation considers the approximate decomposition of a given matrix into the product of three matrices where a usual matrix product is followed by a tropical product. This formulation has a very interesting interpretation in terms of the learning of the utility functions of multiple users. We also present numerical results illustrating the effectiveness of the proposed algorithms, as well as an application to recommendation systems with promising results.

Related papers

• Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications [30.659400341011004]
  We provide rigorous equations characterizing the Bayes-optimal learning performance from a number of samples. We mathematically establish predictions obtained via non-rigorous methods from statistical physics.
  arXiv  Detail & Related papers  (2025-03-18T10:36:30Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  We consider matrix factorization (MF) with certain constraints, which finds wide applications in various areas. We develop a Bayesian approach to MF with an efficient message passing implementation, called UAMPMF. We show that UAMPMF significantly outperforms state-of-the-art algorithms in terms of recovery accuracy, robustness and computational complexity.
  arXiv  Detail & Related papers  (2022-07-31T12:09:32Z)
• Weighted Low Rank Matrix Approximation and Acceleration [0.5177947445379687]
  Low-rank matrix approximation is one of the central concepts in machine learning. Low-rank matrix completion (LRMC) solves the LRMA problem when some observations are missing. We propose an algorithm for solving the weighted problem, as well as two acceleration techniques.
  arXiv  Detail & Related papers  (2021-09-22T22:03:48Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation [13.37650464374017]
  We develop a framework for nonparametric trace regression models via structured sign series representations of high dimensional functions. In the context of matrix completion, our framework leads to a substantially richer model based on what we coin as the "sign rank" of a matrix.
  arXiv  Detail & Related papers  (2021-05-04T22:20:00Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  We consider an adversarially-trained version of the nonnegative matrix factorization. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices.
  arXiv  Detail & Related papers  (2021-04-10T13:13:17Z)
• Projection techniques to update the truncated SVD of evolving matrices [17.22107982549168]
  This paper considers the problem of updating the rank-k truncated Singular Value Decomposition (SVD) of matrices subject to the addition of new rows and/or columns over time. The proposed framework is purely algebraic and targets general updating problems. Results on matrices from real applications suggest that the proposed algorithm can lead to higher accuracy.
  arXiv  Detail & Related papers  (2020-10-13T13:46:08Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)

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.