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 is sufficient to accomplish certain
tasks including autonomous clustering.
more »
« less
The random component-wise power method
This paper considers a random component-wise 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 component-wise updates converge in the
mean-squared 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 a ect the convergence rate of the randomized updates unlike the regular
power method. In particular, it is shown that the rate of convergence is a ected by the phase of the eigenvalues
in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over
positive ones. As an application, this study considers a reformulation of the component-wise 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 large-scale distributed data when computing an arbitrary
rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed
algorithms under di erent parameter settings.
more »
« less
- Award ID(s):
- 1712633
- NSF-PAR ID:
- 10148054
- Date Published:
- Journal Name:
- Proc. SPIE 11138, Wavelets and Sparsity XVIII
- Page Range / eLocation ID:
- 57
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)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 mean-squared 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 node-asynchronous updates are combined with polynomial filtering in order to obtain a spectral clustering for directed networks. The convergence is also verified with numerical simulations.more » « less
-
We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, 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 linear-quadratic convergence rates of state-of-theart sub-sampled 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 remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component. We discuss and illustrate applications to linear and quadratic programming, as well as logistic regression and other generalized linear models.more » « less
-
This paper considers a node-asynchronous 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 non-diagonalizable 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 1-hop localized on the graph irrespective of the order of the filter. The method is shown to converge in the mean-squared 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.more » « less
-
This work considers the minimization of a general convex function f (X) over the cone of positive semi-definite matrices whose optimal solution X* is of low-rank. Standard first-order 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 well-conditioned 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.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1117/12.2530511
