Matrix Factorization over Max-Times Algebra for Data Mining

Among many different ways one can define matrix multiplication, the standard and Boolean cases are the most thoroughly studied. In this work we introduce matrix multiplication over max-times algebra, which is the set of nonnegative real numbers endowed with standard multiplication, but with addition being replaced by the maximization operation. The main objective of the thesis is to develop efficient factorization algorithms for this newly defined matrix multiplication.

We propose several methods for solving this problem. The choice of a particular algorithm depends on the nature of the data, in particular its density. The sparser the matrices, the closer their max-multiplication is to the standard matrix multiplication, and for extremely sparse data even an algorithm for nonnegative matrix factorization can be quite good. However, for other cases algorithms that are specifically tailored for max-times data are required.
The max matrix factorization problem is hard, and solving the problem precisely for large input sizes is infeasible, which means that approximate methods should be sought. It turned out in the experiments that the most promising approach is to relax the objective in such way that it becomes differentiable, after which convex optimization algorithms (e.g. gradient descent) can be used. This produces relatively good results when the max-times structure is present in the data.