Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The submission "A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations" develops a new algorithm for the problem of computing a PSD factorization of a nonnegative matrix. This generalizes the nonnegative matrix factorization (NMF) problem and is of interest both as a succinct representation of data, but also due to connections to lifted representations of convex sets and problems in quantum information. The algorithm is a non-obvious generalization of a well-known method for NMF due to Lee and Seung to the matrix setting. The authors establish that the updates are non-increasing for the squared loss objective and the fixed points satisfy the KKT conditions, if the iterates are initialized to be positive definite, and show that the algorithm can be used in practice via numerical experiments.
main_review: Originality: This paper introduces an algorithm for PSD factorization that is new, and generalizes a widely-used algorithm for nonnegative matrix factorization. The work is well situated in the existing literature on algorithms for PSD factorization, and what is different about this method (when compared to, for instance, directly solving the PSD constrained least squares subproblems via IPM or Burer-Monetiro-style factorization methods) is clearly articulated. 

Quality: The submission appears to be correct. It motivates the algorithm (via the MM framework and its connection to the Lee-Seung algorithm), describes it clearly, and establishes key results about the algorithm. Some of the proofs are deferred to the supplementary material. It would perhaps have been nice to include the 3 key steps involved in proving Lemma 3 in the main body (normalizing so B=I, the use of Lieb's theorem, and the use of the inequality tr(AB)^2<= tr(A^2)tr(B^2)), to make the body even more self-contained. 

In the experimental section, it would have been nice to discuss two issues a little more:
-- the addition of small positive quantities for "conditioning purposes" is a little mysterious, and may deserve more discussion. Is this required in the LS (commutative case)? Can this damped update also be interpreted naturally in the MM framework and shown to converge, etc?
-- what is the stopping criterion used and/or suggested, or are the experiments just run for a fixed number of iterations? Are there any interesting issues related to choosing a stopping criterion?

Clarity: The paper is clearly written and easy to follow. 

I found a few minor typos:
-- Line 72: "if it present" should be "if it is present"
-- Line 111: consider "Moreover, a PSD factorization..." rather than "Moreover, given a PSD factorization..."
-- Line 161: "how to the MMU" should be "how the MMU"
I also felt that the proof of Lemma 3 could be streamlined a little. The concavity of 
$$f(X)= \textrm{tr}(ZX^{1/2}ZX^{1/2})$$
(a very special case of Lieb's concavity theorem) and the fact that $f$ is positively homogeneous of degree one in X, implies that this function satisfies, $f(X_1+X_2 + \cdots + X_k) >= f(X_1)+f(X_2) + \cdots + f(X_k)$ which is really the first main inequality used. This saves the argument by induction, etc. 

Significance: The authors devote a significant amount of space to motivating the PSD factorization problem. As a tool in studying semidefinite representations of convex bodies, and as a tool in the correlation generation problem, PSD factorization is a well-known tool. It is, perhaps, less widely used as a concise representation of nonnegative data. The last paragraph of the introduction, discussing the interpretation of a PSD factorization in this context, is welcome, and may help stimulate further use of PSD factorizations in this context.

The main theoretical results of the paper focus on the case where the computed factors are positive definite. This is appropriate in the context of representing nonnegative data, but is not always appropriate in the context of PSD lifts of polytopes, for instance, where the factors are never positive definite (since the slack matrix always has some zero entries). To what extent it is possible to extend the algorithm and/or its analysis to the case where the matrices are not initialized to be positive definite? Certainly any discussion in this direction would be welcome, and could further extend the significance of the results in this submission.

Update: after reading the other reviews and the response of the authors, I have not changed my (positive) assessment of this paper. 
limitations_and_societal_impact: The authors have adequately addressed the limitations of the work, by keeping it focused on precisely formulated mathematical statements (the limitations of which are inherent in their precise formulation).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem fo finding a certain type positive semidefinite (PSD) factorization of a matrix with non-negative entries. The main result is a new algorithm for this problem which has some nice properties. The authors begin by describing various applications the PSD factorization problem. One special case is the problem of non-negative matrix factorization, which corresponds to the constraint that the PSD matrices are diagonal. Then, the authors described their method which falls in the majorization-minimization framework where the majorization is based on a matrix version of the geometric mean. The authors show that that the iterates of this algorithm preserve certain structural properties of the initialization point, and that in the case of diagonally restricted matrices, it reduces to the well-known Lee-Seung algorithm for non-negative matrix factorizations. Some numerical results are also provided. 


main_review: I enjoyed reading this paper. I think the authors did a good job of explaining the problem and some of its applications, and then clearly describing their contribution and the connection with prior work. 
limitations_and_societal_impact:  I think the discussion is appropriate.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies algorithms for computing rank r positive semi-definite decompositions of a matrix with non-negative entries. They cast this non-convex problem as an alternating minimization problem and propose an update rule that is guaranteed to be non-increasing. They also show that all the fixed-points of their algorithm satisfy the first order optimality conditions for the objective. 
main_review: Given an mxn matrix $X$ with non-negative entries, there is a rank $r$ positive semi-definite decomposition for the matrix $X$ if there exist $r \times r$ positive semi-definite matrices $A_1, \ldots, A_m$ and $B_1, \ldots, B_n$, one for each row and column respectively such that for all $i,j$ : $X_{ij} = \text{tr}(A_i B_j)$. This is a generalization of non-negative matrix factorization where all the r x r positive semi-definite matrices $A_1, ..., A_m$ and $B_1, ..., B_n$ have an additional constraint that they should be diagonal matrices. It is clear that relaxing the constraint of diagonality increases the expressibility and therefore the positive semi-definite rank of the matrix may be much smaller than the non-negative rank of a matrix. The problem is cast in an alternating-minimization framework where we fix $A_1,...,A_m$ and optimize over $B_1,...,B_n$ and then fix $B_1,...,B_n$ and optimize over $A_1,...,A_m$ until we reach a fixed point. Fixing matrices $A_1,...,A_m$ makes the objective to be an "independent" sum of contributions of the matrices $B_1,...,B_n$ and therefore the problem that needs to be solved is optimizing only over a single positive semi-definite matrix. This is the problem they solve. 

They give an update rule for this problem and show that their updates never increase the objective value. The update rule is simple and falls-back to Lee-Seung's update rule when initialized with diagonal matrices. An advantage of the update rule presented by the authors is that it preserves the block diagonal structure of the initial iterates. The authors also argue that the fixed points of their update rule satisfy KKT conditons for the objective. They also run experiments using their algorithms and show that the solutions converge to an optimal decompositon with sufficient number of random initializations.

Strengths:
- Paper is written well with enough motivation for why the problem is important to be solved and how it relates to other important problems.
- Introduces new techniques to the problem where the earlier works were only using Projected Gradient Method or Coordinate Descent.
- Update rule falling back to the current algorithms for non-negative matrix factorization when initialized with diagonal matrices is good as this means their update rule is a natural extension of the earlier work.
- Proofs are concise and clear.

Weaknesses:
- Experiments : It would be good to compare with the earlier coordinate descent and projected gradient methods.
- Not having any bounds on how quick the algorithm converges to a fixed point. I understand it may be hard to get any analysis at all. Do you have any ideas here?

Questions:
1. You mention in the experiments that with sufficient initializations, the algorithm for PSD factorization of a distance matrix is close to being exact. It does seem like all other initializations converge to some fixed point from your graphs. Is there anything interesting at all about the factorizations your algorithm converges to in these other initializations?

2. Does rank of the optimal decomposition play any role at all? Say for example, in the distance matrix decomposition, the optimal PSD-matrices all have rank 1. Does the algorithm converge faster for instances with low rank optimal decompositions.

3. I don't think it is fair to call the decomposition in Figure 3 as building blocks. They are just the reconstructions for the components in the eigen decomposition for that particular image unlike the building blocks that are same for all the images in the case of non-negative matrix factorization. That is why I don't agree the latent space being called "infinite dimensional". Am I missing something here? This isn't particularly a weakness -- I am just looking for a clarification.

Suggestions:
- $ \text{tr}(XY)^2 \le \text{tr}(X^2)\text{tr}(Y^2)$ is just the Cauchy-Schwarz inequality for the standard inner-product on the space of symmetric matrices. So you need not use von Neumann trace inequality and can obtain an easier proof.

Typos/Mistakes:
- Line 122 pace -> space
- Line 161 "how to the" -> "how the"
- Line 211 $f$ -> $F$
- Define $\mathcal{A}^{\mathsf{T}}$ before its use
- Line 440 In the display equation, $^2$ is missing

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper suggest an approach to PSD (positive-semidefinite) matrix factorisation (NMF), which generalizes the algorithm of Lee and Seung’s (Multiplicative Update algorithm, MUa) to what they call Matrix Multiplicative Update (MMU) algorithm.  It is shown that the fixed points of the MMU algorithm correspond to the KKT optimality conditions for the the problem (problem 8 in the main body of the paper). While there are papers showing similar result for the non-negative matrix factorization (https://arxiv.org/abs/2002.11323), the present paper simplified the proof technique. This is accompanied by code, which uses a "damped variant" of the algorithm (not covered by the analysis?), and is shown to work on an 361 x 2429 matrix.

main_review: This paper suggest an approach to PSD (positive-semidefinite) matrix factorisation (NMF), which generalizes the algorithm of Lee and Seung’s (Multiplicative Update algorithm, MUa) to what they call Matrix Multiplicative Update (MMU) algorithm. The idea of the MMU algorithm is to choose carefully a surrogate function and apply SM to the convex SDP problem (12) which is equivalent to the original formulation of the PSD factorisation problem (8). This is quite elegant. The main theorem (Theorem 1) shows that what essentially is the vectorisation operation from the space of symmetric rank r matrices to m dimensional real vector space allows one to have an objective function to be minimised that does not increase under the update rule they provide. 

Originality:

While there are some recent algorithms for PSD factorization (utilizing SDP hierarchies for NCPOP in https://link.springer.com/article/10.1007/s10208-018-09410-y, or heuristic approaches https://arxiv.org/abs/1707.07953), the proposed algorithm nicely combines some scalability and some guarantees. Notably, authors prove that 
-- if one starts with a feasible solution, the iterations lead to a feasible solution
-- if one terminates with a feasible solution, then the fixed point of the iteration satisfies the KKT conditions for the the problem (problem 8 in the main body of the paper). 

Quality:

The analysis is of interest. Similar (or stronger) result had been available only for the non-negative matrix factorization (which is a special case of the problem with diagonal PSD matrices; https://arxiv.org/abs/2002.11323), plus the present paper simplified the proof technique. 

This is accompanied by code, which uses a "damped variant" of the algorithm (not covered by the analysis?), and is shown to work on an 361 x 2429 matrix. The code is ok -- the key method is pasted below.

Clarity:

The 9-page writeup is mostly describing the motivation (pages 1-3) and related work (pages 4 and 5), in a rather confusing manner. (E.g. Section "Existing work" does not mention the "MM Framework".) While one may see the lengthy motivation as adding an "interdisciplinary" aspect, it may actually detract from the paper's value. 

Still, there is a proof of Theorem 1, which is quite elegant. The technical analysis is relatively well written, although the notation can be puzzling occasionally, for example the operator T introduced in (18) is not motivated. The definition of W is repeated several times but this actually eases the readability of the proof of Theorem 1. (Notice that Appendix A contains Lemma 3 which is a technical requirement for the proof of Theorem 1 and Appendix B contains Lemma 3 which is proves Theorem 2.)

Significance:

For the "PSD-Rank community", this will be an important paper. Considering that even papers by Nesterov on the subject (e.g. https://arxiv.org/abs/1707.07953) have less than 10 citations, though, it's not clear whether this is of wide interest. 

Minor comments:

Neither the iteration complexity of the algorithm, nor the computational complexity of a single update is discussed in detail. 

The discussion of related work on lines 173-180 is flawed: the use of Cardano's method for a cubic polynomial in a step of a coordinate descent on has been first proposed by https://arxiv.org/abs/1506.08568, rather than by Nesterov (https://arxiv.org/abs/1707.07953). See the paragraph "The Closed-Form Step" in https://arxiv.org/abs/1506.08568. 

A detailed table comparing the MMU algorithm with the relevant existing work (part of it described in Section 2) could have been provided.

The matrix geometric mean is used in the main algorithm but a fully geometric picture from the viewpoint of Riemannian geometry is not presented although briefly motivated around line 216.

There is a typo in line 161.


--
def update_blockmultiplicative(A,B,X):
    """
    Updates the factor B via the multiplicative updates
    """
    
    l = len(B)
    d = B[0].shape[0]
    
    AAB = compute_blockAAB(A,B)
    AtX = compute_block(A,X)
    
    # Invert AAB
    AABinv = []
    for k in range(l):
        AABinv.append(np.zeros(B[k].shape))
        for i in range(d):
            AABinv[k][i,:,:] = np.linalg.inv(AAB[k][i,:,:])
    
    # Compute the geometric mean with a damping term
    H = []
    for k in range(l):
        H.append(np.zeros(B[k].shape))
        for i in range(d):
            H[k][i,:,:] = matrix_gm(AABinv[k][i,:,:],B[k][i,:,:])
            
    # Update B_new
    B_new = []
    for k in range(l):
        B_new.append(np.zeros(B[k].shape))
        for i in range(d):
            M = ( H[k][i,:,:] @ AtX[k][i,:,:] ) @ H[k][i,:,:].T
            B_new[k][i,:,:] = M
            
    return B_new
limitations_and_societal_impact: This will not have any societal impact.
review_title: null

Meta-review: The proposed method for computing a positive semidefinite factorization of a non-negative matrix and its analysis are original and of interest to the community. The paper is also clearly written and motivated. The authors are encouraged to take into account the reviewers' comments when preparing the revision.
Decision: Accept (Poster)