Algorithms for approximate subtropical matrix factorization

DOI10.1007/S10618-018-0599-1zbMATH Open1458.68169arXiv1707.08872OpenAlexW2740287343WikidataQ128724709 ScholiaQ128724709MaRDI QIDQ2218339FDOQ2218339

Authors: Sanjar Karaev, Pauli Miettinen 

Publication date: 15 January 2021

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: Matrix factorization methods are important tools in data mining and analysis. They can be used for many tasks, ranging from dimensionality reduction to visualization. In this paper we concentrate on the use of matrix factorizations for finding patterns from the data. Rather than using the standard algebra -- and the summation of the rank-1 components to build the approximation of the original matrix -- we use the subtropical algebra, which is an algebra over the nonnegative real values with the summation replaced by the maximum operator. Subtropical matrix factorizations allow "winner-takes-it-all" interpretations of the rank-1 components, revealing different structure than the normal (nonnegative) factorizations. We study the complexity and sparsity of the factorizations, and present a framework for finding low-rank subtropical factorizations. We present two specific algorithms, called Capricorn and Cancer, that are part of our framework. They can be used with data that has been corrupted with different types of noise, and with different error metrics, including the sum-of-absolute differences, Frobenius norm, and Jensen--Shannon divergence. Our experiments show that the algorithms perform well on data that has subtropical structure, and that they can find factorizations that are both sparse and easy to interpret.

Full work available at URL: https://arxiv.org/abs/1707.08872

Recommendations

• Relative-Error $CUR$ Matrix Decompositions
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
• Algorithms and applications for approximate nonnegative matrix factorization
• Nonnegative matrix factorization: model, algorithms and applications
• A very fast algorithm for matrix factorization

zbMATH Keywords

data miningmatrix factorizationstropical algebramax-times algebra

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Pattern recognition, speech recognition (68T10) Factorization of matrices (15A23) Approximation algorithms (68W25) Max-plus and related algebras (15A80)

Cites Work

• The University of Florida sparse matrix collection
• Title not available (Why is that?)
• Algorithms and applications for approximate nonnegative matrix factorization
• On the complexity of nonnegative matrix factorization
• Non-negative matrix factorization with sparseness constraints
• Title not available (Why is that?)
• Learning the parts of objects by non-negative matrix factorization
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• Linear independence over tropical semirings and beyond
• Densities of idempotent measures and large deviations
• Large deviations techniques and applications.
• Linear and combinatorial optimization in ordered algebraic structures
• Minimax algebra
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• Max-algebra: The linear algebra of combinatorics?
• The complexity of tropical matrix factorization
• Introduction to Discrete Event Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On semigroups of matrices over the tropical semiring
• Pattern Properties and Spectral Inequalities in Max Algebra
• Title not available (Why is that?)
• Methods and applications of \((\max,+)\) linear algebra
• Using underapproximations for sparse nonnegative matrix factorization
• The ultimate rank of tropical matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• A condition for the strong regularity of matrices in the minimax algebra
• Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
• The QR Decomposition and the Singular Value Decomposition in the Symmetrized Max-Plus Algebra Revisited
• Title not available (Why is that?)
• Understanding complex datasets. Data mining with matrix decompositions

Cited In (2)

• Some facts about the choice of the weighting matrices in Larimore type of subspace algorithms
• Descriptive matrix factorization for sustainability. Adopting the principle of opposites

Uses Software

• SparseMatrix
• UMDES
• Multilinear Engine
• NMF MATLAB Toolbox

This page was built for publication: Algorithms for approximate subtropical matrix factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218339)