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, Paul 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, 438(4), pp. 1863-1882, 2013
- Download
-
[Home]