Low-rank matrix reconstruction and clustering via approximate message passing
We study the problem of reconstructing low-rank matrices from their noisy observations. We formulate the problem in the Bayesian framework, which allows us to exploit structural properties of matrices in addition to low-rankedness, such as sparsity. We propose an efficient approximate message passing algorithm, derived from the belief propagation algorithm, to perform the Bayesian inference for matrix reconstruction. We have also successfully applied the proposed algorithm to a clustering problem, by reformulating it as a low-rank matrix reconstruction problem with an additional structural property. Numerical experiments show that the proposed algorithm outperforms Lloyd's K-means algorithm.
Review of "Low-rank matrix reconstruction and 
      clustering" This paper contributes a new algorithm for low-rank 
      matrix reconstruction which is based on an application of Belief 
      Propagation (BP) message-passing to a Bayesian model of the reconstruction 
      problem. The algorithm, as described in the "Supplementary Material", 
      incorporates two simplifying approximations, based on assuming a large 
      number of rows and columns, respectively, in the input matrix. The 
      algorithm is evaluated in a novel manner against Lloyd's K-means algorithm 
      by formulating clustering as a matrix reconstruction problem. It is also 
      compared against Variational Bayes Matrix Factorization (VBMF), which 
      seems to be the only previous message-passing reconstruction algorithm. 
      Cons There are some arguments against accepting the paper. 
      Because a new algorithm is being evaluated on a non-standard problem 
      (clustering encoded as matrix factorization), it is not easy to 
      interpolate the experimental results to predict how the algorithm would 
      perform on more conventional matrix reconstruction problems. For instance, 
      two references appear to be cited for VBMF, which are Lin and Teh (2007); 
      and Raiko, Ilin and Karhunen (2007). Both of these papers use the Netflix 
      dataset to evaluate their algorithm against predecessors. It would be 
      ideal if the present paper had used the same dataset. Although BP is 
      usually more accurate than Variational, evaluating the present BP variant 
      using a new criterion creates doubt surrounding its actual 
      competitiveness. Even if Netflix or a similar dataset can't be used, the 
      authors should explain in the paper why this is the case. The 
      algorithm itself appears to be a more or less straightforward application 
      of BP to a problem which had been previously addressed with Variational 
      Message Passing. Although new, it is not exactly groundbreaking. The most 
      interesting part of it, to me, is the approximations which are introduced 
      in the limit $N\to\infty$ and $m\to\infty$, where $m \times N$ is the 
      dimensions of the input matrix. However, the validity of these 
      approximations, which are only described in supplementary material, is 
      never directly tested, and I think they could be explained a bit more 
      clearly. There are some serious problems regarding the citation of 
      prior work. When I first read the paper, I thought that it was introducing 
      the application of matrix factorization to clustering as an original 
      contribution. The text of the abstract and Section 2.2 give this 
      impression. I felt betrayed when I learned from other reviewers that the 
      connection is well-known. I don't see a good reason why the paper would 
      not make this clear to the reader. If it is too well-known to cite any 
      particular reference, then one should just say that it is well-known. 
      Otherwise, cite prior work. Also, EP should be cited, since that 
      is usually the name people give to applying BP to continuous classes of 
      distributions, and the relationship with EP to the paper's algorithm 
      should be explained. Relatedly, the main algorithm is most plainly 
      understood as an application of Belief Propagation, but this fact is not 
      mentioned until Section 4.1. It should be mentioned in the abstract. 
      Pros The paper was interesting to read, and presents a new 
      and potentially useful algorithm. The mathematics of the paper was 
      possible to follow, and although I did not replicate it by hand, I got the 
      sense that it would be possible to do so. Although I think it is 
      reasonable to be suspicious of new evaluation criteria, the K-means 
      problem may be sufficiently general to give a fair comparison of the 
      algorithms, and certainly shows a benefit for the new algorithm in the 
      experiments. Clarity I found the early presentation fairly 
      easy to follow. The introduction was clear, as was the summary of earlier 
      work. The fact that the derivation of the algorithm only appears in the 
      Supplemental Material is a drawback. I wish that the derivation could be 
      outlined in the main paper. The experiments section was clear, and 
      although some of the plots show up poorly in black and white, they were 
      still readable. I found it difficult to understand the description 
      of the algorithm, and I was not able to check the correctness of the 
      derivation. The mathematics was the weakest part of this presentation. 
      Even at a very superficial level it was difficult to parse. For instance, 
      I don't understand why factors of $1 / m \tau_w$ appear before each term 
      in equations 9a, 9b, 9d, and 9e. These could be factored out, to make the 
      expressions easier to read. Also, the last two terms in 9b and 9e, 
      respectively, could be combined. There seem to be an excess of 
      hats, tildes, subscripts, and superscripts. For instance, there is a 
      $\tau_w$ but no $\tau$, why not just replace $\tau_w$ by $\tau$? Also, the 
      most important Section 4 contains no p, q, or r, but only \hat{p}, 
      \hat{q}, \hat{r} - why not give readers a break and say at the beginning 
      of the section "We'll be dropping the hats here for brevity"? And the 't' 
      superscripts in the messages seem to be wholly unnecessary. When the left 
      hand side has a "t+1" you just need to change "=" to "\gets" and then you 
      can drop all of the t's. I have a hard time imagining that the algorithm 
      was originally derived by the authors using such cumbersome notation. I 
      would suggest going back to the first notation you used and looking to see 
      if it is simpler. The exposition could be improved: Why not 
      explain that equation 5 is the negative logarithm of equation 2? Or that 
      equation 8 is just equation 2 to the power of $\beta$? Algorithm 2 seems 
      to be almost row-column symmetrical, why not point this out? And even make 
      it half as long, by saying, "then copy and paste these equations, 
      switching u and v"? The meaning of functions in 10 should be 
      explained near their definition. It would be clearer to say "f_\beta is 
      the mean of q_\beta", rather than giving an equation; but if you decide to 
      give an equation, then why not say what it means? At the end of Section 
      4.2, it says "G_\beta(b, \Lambda; p) is a scaled covariance matrix of 
      q_\beta(u; b, \Lambda, p)", but this was not obvious at first, and wasn't 
      even mentioned at the definition of G. None of the messages have 
      \beta subscripts, even though they depend on f and G which have \beta 
      subscripts. But f and G don't depend directly on \beta, only on q_\beta. 
      So it's not clear why these subscripts are propagated only as far as f and 
      G and no further. I would suggest eliminating them entirely, even from q. 
      The parameter \beta is simply a global variable, which is just fine. 
      Before (15) and (16), it will just be necessary to say something like "in 
      the limit \beta \to \infty, f and G take the following form:". On 
      a deeper level, there were other things about the algorithm that I would 
      like to understand better. What is the significance of the m factor in the 
      additive noise variance? Does it play a role in applications of matrix 
      factorization? Does it play a role in the approximation used to derive the 
      algorithm? It seems to be the only thing making the algorithm fail to be 
      row-column symmetrical, is this true? I think the authors know the answer 
      to these questions, but do not comment on them. Other questions: 
      Is it standard to use a tilde to denote column vectors? I didn't 
      understand this at first. Just curious - why is N capitalized, but 
      m lowercase? In section 5, I would like a citation after VBMF-MA 
      to indicate the primary reference guiding the implementation of this 
      competing algorithm. There are two citations for variational matrix 
      factorization appearing earlier in the paper, and it is not clear which is 
      intended (or if it is both). In the supplementary material: For 
      equation 5, I think it would be clearer to write a product of exponentials 
      for the two terms involving $z$, to make it more obvious that one is the 
      pdf. For section 2, I had trouble with the step from equation 14 to 15, 
      regarding big-O of $m$ terms. I am not sure if I just need to think 
      harder, but this is where I got stuck. Also in the supplementary 
      material, at the top of page 2 it says "A technique used in ... is to give 
      an approximate representation of these message in terms of a few number of 
      real-valued parameters". Without reading these references, I am not sure 
      how exactly the approximation described below this text relates to what 
      has been published before. It would be good to clarify the novelty of the 
      algorithm's derivation in the text itself, and even in the main paper. 
      The English is very good, and the meaning always gets across, but 
      there are some places where it reads like it was written by someone not 
      entirely skilled in the use of articles. This can be distracting for some 
      readers. Even in the title - I think it should be something like "Low-rank 
      matrix reconstruction and clustering using an approximate message passing 
      algorithm". For other places, I will make a list of suggestions which may 
      be of use to the authors: p. 1 "Since properties" -> 
      "Since the properties" "according to problems" -. "according to 
      the problem" "has flexibility" - "has enough flexibility" 
      "motivate use of" -> "motivate the use of" p. 2 
      "We present results" -> "We present the results" p. 3 
      "We regard that" -> "We see that" "maximum accuracy 
      clustering" could be italicized "Previous works" -> "Previous 
      work" "ICM algorithm; It" -> "ICM algorithm: it" p. 4 
      "particularized" -> "specialized" p. 5 
      "plausible properties" -> "discernable properties"? p. 
      6 "stuck to bad local minima" -> "stuck in bad local minima"? 
      p. 7 "This is contrastive to that" -> "This is in 
      contrast to the fact that" The Supplementary Material also has 
      some language issues, for instance: p. 2 "of these 
      message" -> "of these messages" "a few number" -> "a few" 
      I liked the diagram in Figure 1 in the Supplementary Material, 
      which I found very helpful. If it is possible to create more diagrams, 
      that would add to the paper.