Sparse approximation of complex networks

This paper considers the problem of recovering a sparse approximation A is an element of R-nxn of an unknown (exact) adjacency matrix A(true) for a network from a corrupted version of a communicability matrix C = exp(A(true)) +N is an element of R-nxn, where N denotes an unknown "noise matrix". We consider two methods for determining an approximation A of A(true) : (i) a Newton method with soft-thresholding and line search, and (ii) a proximal gradient method with line search. These methods are applied to compute the solution of the minimization problem arg min(A is an element of R)(nxn) {parallel to exp(A) - C parallel to(2)(F) + mu parallel to vec(A)parallel to(1)}, where mu > 0 is a regularization parameter that controls the amount of shrinkage. We discuss the effect of mu on the computed solution, conditions for convergence, and the rate of convergence of the methods. Computed examples illustrate their performance when applied to directed and undirected networks.