中文
Published date:2014-09-22    Provided by:School of Science
 Title: Optimization Models and Methodologies for Binary/Integer Matrix Factorization

Guest Speaker: Prof. Peng Jiming (University of Houston, USA)

Time: 2014-7-25, 10:30 - 12:00

Location: Room 7215, School of Science  


Content & Introduction:

In general, binary/integer matrix factorization (BMF/IMF) refers to the problem of finding a matrix product of two binary low rank matrices such that the difference between the matrix product and a given binary matrix is minimal. BMF has served as an important tool in dimension reduction for high-dimensional data sets with binary attributes and been successfully applied in myriad applications.  BMF has been studied and many results have been reported. However, even for the very specific case where both the involved matrices are of rank 1, how to obtain a good approximation effectively remains a challenge.

   In this talk, we first introduce two specific variants of constrained BMF (CBMF) where the matrix product is required to be binary, and propose alternating update procedures for CBMF. In every iteration of the proposed procedure, we solve a specific binary linear programming (BLP) problem to update the involved matrix argument. We explore the interrelation between the BLP subproblem and clustering to develop an effective 2-approximation algorithm for CBMF when the underlying matrix has a very low rank. The proposed algorithm improves substantially over existing algorithms for BMF in the literature.  For matrices of high rank, we develop a linear-time approximation algorithm for CBMF based on randomization techniques and estimate the solution quality. We present numerical experiments to illustrate the efficacy of the new model and the efficiency of the new algorithms.