Paper ID sheet UCL-INMA-2010.106

Title

Iterative methods for low rank approximation of graph similarity matrices

Authors
T. P. Cason, P.-A. Absil, P. Van Dooren
Abstract
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
Status
Linear Algebra and Its Applications, Volume 438, Issue 4, 15 February 2013, Pages 1863-1882
Download
BibTeX entry
@ARTICLE{CasAbsDoo2013,
  author = "T. P. Cason and P.-A. Absil and P. Van Dooren",
  title = "Iterative methods for low rank approximation of graph
  similarity matrices",
  journal = "Linear Algebra Appl.",
  fjournal = "Linear Algebra and its Applications",
  year = 2013,
  volume = "438",
  number = "4",
  pages = "1863--1882",
  doi = "10.1016/j.laa.2011.12.004",
}
[Home]