Algorithms for approximate subtropical matrix factorization

DOI10.1007/S10618-018-0599-1MaRDI QIDQ2218339zbMATH OpenOpenAlexWikidataFDO

Authors Sanjar Karaev, Pauli Miettinen

Publication date 15 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• NMF MATLAB Toolbox
• Multilinear Engine
• UMDES
• SparseMatrix

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)