B. De Schutter, J. Schepers, and I. Van Mechelen, "On algorithms for a binary-real (max,×) matrix approximation problem," Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, California, pp. 5168-5173, Dec. 2006.
We consider algorithms to solve the problem of approximating a given matrix D with the (max,×) product of a binary (i.e., a 0-1) matrix S and a real matrix P: minS,P || S · P - D ||. The norm to be used is the l1, l2 or l∞ norm, and the (max,×) matrix product is constructed in the same way as the conventional matrix product, but with addition replaced by maximization. This approximation problem arises among others in data clustering applications where the maximal component instead of the sum of the components determines the final result. We propose several algorithms to address this problem. The binary-real (max,×) matrix approximation problem can be solved exactly using mixed-integer programming, but since this approach suffers from combinatorial explosion we also propose some alternative approaches based on alternating nonlinear optimization, and a method to obtain good initial solutions. We conclude with a simulation study in which the performance and optimality of the different algorithms are compared.