Paper ID sheet UCL-INMA-2010.106


Iterative methods for low rank approximation of graph similarity matrices

T. P. Cason, P.-A. Absil, Paul Van Dooren
In this paper, we analyze an algorithm to compute a low-rank approximation of the similarity matrix $\mathbf{S}$ introduced by Blondel \emph{et al.} in [Blondel et al.,SIAM Review 46 (4) (2004) 647-666]. This problem can be reformulated as an optimization problem of a continuous function $\Phi(S)=\mathrm{trace}(S^T\mathcal{M}^2(S)}$ where $S$ is constrained to have unit Frobenius norm, and $\mathcal{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 [Blondel et al.,SIAM Review 46 (4) (2004) 647-666].
Key words
graph theory; node to node similarity; trace maximization; low-rank approximation; algorithm; set of low-rank matrices
Linear Algebra and its Applications, 438(4), pp. 1863-1882, 2013