The notion of graph shift, introduced recently in graph signal processing, extends many classical signal processing techniques to graphs. Its practical importance follows from its localization: a single graph shift requires nodes to communicate only with their neighbors. However, communications should happen simultaneously, which requires a synchronization over the graph. In order to overcome this restriction, recent studies consider a random asynchronous variant of the graph shift, which is also suitable for autonomous networks. A graph signal under this randomized scheme is shown to converge (under mild conditions) to an eigenvector of the eigenvalue 1 of the operator even if the operator has other eigenvalues with magnitudes larger than unity. If the eigenvalue 1 does not exist, the operator can be easily normalized in theory. However, in practice, the normalization requires one to know the (dominant) eigenvalues, which may not be possible to obtain in large autonomous networks. To eliminate this limitation, this study considers the use of a nonlinearity in the updates making the scheme similar in spirit to the Hopfield neural network model. Our simulation results show that a graph signal still approaches the eigenvector of the dominant eigenvalue although the convergence is not exact. Nevertheless, approximation ismore »
The random componentwise power method
This paper considers a random componentwise variant of the unnormalized power method, which is similar
to the regular power iteration except that only a random subset of indices is updated in each iteration. For
the case of normal matrices, it was previously shown that random componentwise updates converge in the
meansquared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix
having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that
the eigenvalue gap does not directly aect the convergence rate of the randomized updates unlike the regular
power method. In particular, it is shown that the rate of convergence is aected by the phase of the eigenvalues
in the case of random componentwise updates, and the randomized updates favor negative eigenvalues over
positive ones. As an application, this study considers a reformulation of the componentwise updates revealing a
randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized
data matrix. The algorithm is also extended to handle largescale distributed data when computing an arbitrary
rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed
algorithms under dierent parameter settings.
 Award ID(s):
 1712633
 Publication Date:
 NSFPAR ID:
 10148054
 Journal Name:
 Proc. SPIE 11138, Wavelets and Sparsity XVIII
 Page Range or eLocationID:
 57
 Sponsoring Org:
 National Science Foundation
More Like this


In recent years the convergence behavior of random node asynchronous graph communications have been studied for the case of undirected graphs. This paper extends these results to the case of graphs having arbitrary directed edges possibly with a nondiagonalizable adjacency matrix. Assuming that the graph operator has eigenvalue 1 and the input signal satisfies a certain condition (which ensures the existence of fixed points), this study presents the necessary and sufficient condition for the meansquared convergence of the graph signal. The presented condition depends on the graph operator as well as the update probabilities, and the convergence of the randomized asynchronous updates may be achieved even when the underlying operator is not stable in the synchronous setting. As an application, the nodeasynchronous updates are combined with polynomial filtering in order to obtain a spectral clustering for directed networks. The convergence is also verified with numerical simulations.

We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a selfconcordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linearquadratic convergence rates of stateoftheart subsampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remainsmore »

This paper considers a nodeasynchronous implementation of rational (“IIR”) filters on graphs, in which the nodes are assumed to wake up randomly and independently from each other, and communicate only with their immediate neighbors. The underlying graph is allowed to be directed, possibly with a nondiagonalizable adjacency matrix. Since the nodes are allowed to act independently, the proposed implementation is practical for very large or autonomous networks where synchronization is difficult to achieve. Furthermore, the proposed algorithm is 1hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the meansquared sense under a boundedness assumption on the filter as well as the graph operator. The result follows from the convergence of a more general randomized asynchronous state recursion, which is also presented in this paper. The algorithm is simulated on a random geometric graph, which numerically verifies the convergence.

This work considers the minimization of a general convex function f (X) over the cone of positive semidefinite matrices whose optimal solution X* is of lowrank. Standard firstorder convex solvers require performing an eigenvalue decomposition in each iteration, severely limiting their scalability. A natural nonconvex reformulation of the problem factors the variable X into the product of a rectangular matrix with fewer columns and its transpose. For a special class of matrix sensing and completion problems with quadratic objective functions, local search algorithms applied to the factored problem have been shown to be much more efficient and, in spite of being nonconvex, to converge to the global optimum. The purpose of this work is to extend this line of study to general convex objective functions f (X) and investigate the geometry of the resulting factored formulations. Specifically, we prove that when f (X) satisfies the restricted wellconditioned assumption, each critical point of the factored problem either corresponds to the optimal solution X* or a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a geometric structure of the factored formulation ensures that many local search algorithms can converge to the global optimum with random initializations.