Matrix factorization with Binary Components
Motivated by an application in computational biology, we consider low-rank matrix factorization with {0, 1}-constraints on one of the factors and optionally convex constraints on the second one. In addition to the non-convexity shared with other matrix factorization schemes, our problem is further complicated by a combinatorial constraint set of size 2 m·r , where m is the dimension of the data points and r the rank of the factorization. Despite apparent intractability, we provide − in the line of recent work on non-negative matrix factorization by Arora et al. (2012)− an algorithm that provably recovers the underlying factorization in the exact case with O(mr2 r + mnr + r 2 n) operations for n datapoints. To obtain this result, we use theory around the Littlewood-Offord lemma from combinatorics.
The paper presents an algorithm for low-rank matrix 
      factorization with constraints on one of the factors should be binary. The 
      paper has several novel contributions for this problem. The algorithm 
      guarantees the exact solution with the time complexity of O(mr2^r+mnr), 
      where previous approach (E. Meeds et al., NIPS 2007) uses MCMC algorithm 
      so that it cannot guarantee a global convergence. Under additional 
      assumptions on the binary factor matrix T, the uniqueness of T is proved 
      which means that each data point has a unique representation with the 
      columns of T. Using Littlewood-Offord lemma, the paper computes a 
      theoretical speed-up factor for their heuristic of the candidate binary 
      vector set reduction step. I summarize the strengths (+) and 
      weaknesses (-) of this paper. Quality (+) The proposed algorithm 
      exhaustively searches all candidates of binary vectors whose time 
      complexity is only exponential in the rank of the matrix by its 
      algorithmic procedure, and later a heuristic of the candidate set 
      reduction is suggested. Analysis of uniqueness and time complexity of the 
      algorithm is appropriate to support the algorithm. (-) I’m not sure this 
      theoretically well-supported algorithm actually works better than the 
      previous approach (E. Meeds et al., NIPS 2007), since the paper doesn’t 
      provide empirical comparison between them. Is this comparison is possible? 
      As a minor comment about the algorithm, is there any reason to use the 
      vector p in each algorithms? It seems that this vector does not contribute 
      to the proof of theories. Clarity (+) It is easy to follow the 
      overall procedure of the algorithm and its theoretical justification. (-) 
      In my opinion, the statements about a non-negative variant in the section 
      2.3 is obvious and unnecessary, and seems to be not connected with other 
      contents. Originality (+) This is a novel contribution for matrix 
      factorization. The algorithm is completely different from the previous 
      one, and guarantees the uniqueness of the solution. Important references 
      about matrix factorization with binary matrices are included in the paper. 
      Significance: (+) Uniqueness of the solution may be useful for 
      many problems whose representation of each data points should be unique, 
      e. g. DNA sequence analysis, even if in most case, data has noise so that 
      this uniqueness property for the exact case does not satisfy. The paper 
      provides a unique theoretical behavior of matrix factorization with one 
      binary factor matrix. (-) As I mentioned earlier, empirical comparison 
      with the existing work is not provided, so I’m not sure the proposed 
      algorithm is better with real-world data. But this comparison is not 
      necessary if it is not possible, since the proposed algorithm is better 
      enough than the existing work with only its theoretical analysis about the 
      uniqueness of the solution.