Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization
Symmetric nonnegative matrix factorization (NMF)-a special but important class of the general NMF-is demonstrated to be useful for data analysis and in particular for various clustering tasks. Unfortunately, designing fast algorithms for Symmetric NMF is not as easy as for the nonsymmetric counterpart, the later admitting the splitting property that allows efficient alternating-type algorithms. To overcome this issue, we transfer the symmetric NMF to a nonsymmetric one, then we can adopt the idea from the state-of-the-art algorithms for nonsymmetric NMF to design fast algorithms solving symmetric NMF. We rigorously establish that solving nonsymmetric reformulation returns a solution for symmetric NMF and then apply fast alternating based algorithms for the corresponding reformulated problem. Furthermore, we show these fast algorithms admit strong convergence guarantee in the sense that the generated sequence is convergent at least at a sublinear rate and it converges globally to a critical point of the symmetric NMF. We conduct experiments on both synthetic data and image clustering to support our result.
[Summary] In this paper, an algorithm for symmetric NMF is proposed.  The key idea of the proposed method is to optimize a matrix by optimizing two different matrices with a penalty term for the equivalence of those two matrices.  The main contribution is to prove the relationship between the original and the modified optimization problems and an equivalent condition about the penalty weight.  Computational experiments show some advantages.  [Related work] Actually, the idea of variable splitting for symmetric NMF is not original, and the same algorithm has been proposed in [10].  The proposed formulation Eq.(3) is completely equivalent to Eq.(15) in [10].  Furthermore, the proposed alternating nonnegative least squares (ANLS) algorithms is the same as in [10].  [Strengths] Several theorems were proven to clarify the relationship between the original and the modified optimization problems.  An equivalent condition about the penalty weight is provided.  Sublinear convergence properties of ANLS and HALS algorithms were proven.  [Weakness]   1) Originality is limited because the main idea of variable splitting is not new and the algorithm is also not new.     2) Theoretical proofs of existing algorithm might be regarded as some incremental contributions.   3) Experiments are somewhat weak:    3-1) I was wondering why Authors conducted experiments with lambda=1.  According to Corollary 1 and 2 lambda should be sufficiently large, however it is completely ignored for experimental setting.  Otherwise the proposed algorithm has no difference from [10].    3-2) In Figure 3, different evaluations are shown in different dataset.  It might be regarded as subjectively selected demonstrations.    3-3) I think clustering accuracy is not very significant because there are many other sophisticated algorithms, and initializations are still very important for nice performance.  It show just the proposed algorithm is OK for some applications.  [Minor points]   -- comma should be deleted at line num. 112: "... + \lambda(u-v), = 0 ...".   -- "close-form" --> "closed-form" at line num.195-196.  --- after feedback --- I understand that the contribution of this paper is a theoretical justification of the existing algorithms proposed in [10].  In that case, the experimental validation with respect to the sensitivity of "lambda" is more important rather than the clustering accuracy.  So Fig. 1 in feedback file is nice to add paper if possible.  I think dropping symmetry is helpful, however it is not new idea that is already being used. So, it will not change anything in practice to use it. Furthermore, in recent years, almost all application researchers are using some application specific extensions of NMF such as sparse NMF, deep NMF, semi-NMF, and graph-regularized NMF, rather than the standard NMF.  Thus, this paper is theoretically interesting as some basic research, but weak from an application perspective.  Finally, I changed my evaluation upper one as:  "Marginally below the acceptance threshold. I tend to vote for rejecting this submission, but accepting it would not be that bad."