报告内容摘要：

In general, binary matrix factorization (BMF or UBMF) 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 numerous applications.  In this talk, we first introduce a new optimization model, called constrained BMF (CBMF)   and discuss its relation to other dimensional reduction models such as  UBMF.
Then we 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 can also provide a 2-approximation to rank-1  UBMF. We also develop a linear-time randomized algorithm for CBMF and estimate the approximation ratio of the obtained solution.  Numerical experiments show that the proposed algorithm for UBMF is able to find better solutions in less CPU time than several other algorithms in the literature, and the solution obtained from CBMF is very close to that of UBMF.

报告人简介：

Jiming Peng received a B.S. degree in computational mathematics and software from Xiangtan University (1987, China), an M.S. degree in computational mathematics from Chinese Academy of Science (1993), and PhD in information technology and system from Delft University of Technology, the Netherlands (2001). From 2001 to 2006, he worked in the department of computing and software at McMaster University as an assistant professor, where was also an associate member of the department of mathematics and statistics at McMaster. His research interest covers several different areas within the field of mathematical programming including numerical methods for variational inequalities and complementary problems, interior-point methods for linear conic optimization, optimization modeling and problem solving in knowledge discovery, decision making and engineering design.