Iterative methods for low rank approximation of graph similarity matrices

In this paper, we analyze an algorithm to compute a low-rank approximation of the similarity matrix S introduced by Blondel et al. in [1]. This problem can be reformulated as an optimization problem of a continuous function Phi(S) = tr(S-T M-2 (S)) where S is constrained to have unit Frobenius norm, and M-2 is a non-negative linear map. We restrict the feasible set to the set of matrices of unit Frobenius norm with either k nonzero identical singular values or at most k nonzero (not necessarily identical) singular values. We first characterize the stationary points of the associated optimization problems and further consider iterative algorithms to find one of them. We analyze the convergence properties of our algorithm and prove that accumulation points are stationary points of Phi(S). We finally compare our method in terms of speed and accuracy to the full rank algorithm proposed in [1]. (C) 2011 Elsevier Inc. All rights reserved.