Capricorn: An Algorithm for Subtropical Matrix Factorization
Sanjar Karaev, Pauli Miettinen · 2016
Max-times algebra, sometimes known as subtropical algebra, is a semi-ring over the nonnegative real numbers where the addition operation is the max function and the multiplication is the standard one.Factorizing a nonnegative matrix over the maxtimes algebra, instead of the standard (nonnegative) one, allows us to find structures and regularities that cannot be easily expressed in the standard algebra.In this paper we study the problem of decomposing matrices over the max-times algebra; in particular, we present our algorithm, Capricorn, to find such decompositions.Experimental evaluation shows that Capricorn finds the max-times structure from data reliably, and furthermore, also identifies areas where it cannot find any structure.