Synchronization on circles and spheres with nonlinear interactions

• URL: http://arxiv.org/abs/2405.18273v1
• Date: Tue, 28 May 2024 15:24:30 GMT
• Title: Synchronization on circles and spheres with nonlinear interactions
• Authors: Christopher Criscitiello, Quentin Rebjock, Andrew D. McRae, Nicolas Boumal,
• Abstract summary: We consider the dynamics of $n$ points on a sphere in $mathbbRd$ ($d geq 2$) which attract each other according to a function $varphi$ of their inner products. When $varphi$ is linear ($varphi(t) = t$, the points converge to a common value (i.e., synchronize) in various connectivity scenarios.
• Score: 6.887244952811574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the dynamics of $n$ points on a sphere in $\mathbb{R}^d$ ($d \geq 2$) which attract each other according to a function $\varphi$ of their inner products. When $\varphi$ is linear ($\varphi(t) = t$), the points converge to a common value (i.e., synchronize) in various connectivity scenarios: this is part of classical work on Kuramoto oscillator networks. When $\varphi$ is exponential ($\varphi(t) = e^{\beta t}$), these dynamics correspond to a limit of how idealized transformers process data, as described by Geshkovski et al. (2024). Accordingly, they ask whether synchronization occurs for exponential $\varphi$. In the context of consensus for multi-agent control, Markdahl et al. (2018) show that for $d \geq 3$ (spheres), if the interaction graph is connected and $\varphi$ is increasing and convex, then the system synchronizes. What is the situation on circles ($d=2$)? First, we show that $\varphi$ being increasing and convex is no longer sufficient. Then we identify a new condition (that the Taylor coefficients of $\varphi'$ are decreasing) under which we do have synchronization on the circle. In so doing, we provide some answers to the open problems posed by Geshkovski et al. (2024).

Related papers

• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  General class of $k$NN graph where the graph affinity is $W_ij = epsilon-d/2 . We prove the point-wise convergence of the $k$NN graph Laplacian to the limiting manifold operator.
  arXiv  Detail & Related papers  (2024-10-30T17:01:00Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Closed expressions for one-qubit states of convex roof coherence measures [0.0]
  We present the analytical expressions for the convex roof coherence measures for one-qubit states. Measures include the coherence of formation, the coherence measure coherence, the coherence rank.
  arXiv  Detail & Related papers  (2023-08-06T13:51:46Z)
• Bounds on Renyi entropy growth in many-body quantum systems [0.0]
  We prove rigorous bounds on the growth of $alpha$-Renyi entropies $S_alpha(t)$. For completely non-local Hamiltonians, we show that the instantaneous growth rates $|S'_alpha(t)|$ can be exponentially larger than $|S'_alpha(t)|$.
  arXiv  Detail & Related papers  (2022-12-14T19:00:01Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Dynamic Ranking and Translation Synchronization [3.946250592943285]
  We study an extension of the emphtranslation synchronization problem, to the dynamic setting. We propose two estimators -- one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator.
  arXiv  Detail & Related papers  (2022-07-04T14:45:12Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• How isotropic kernels perform on simple invariants [0.5729426778193397]
  We investigate how the training curve of isotropic kernel methods depends on the symmetry of the task to be learned. We show that for large bandwidth, $beta = fracd-1+xi3d-3+xi$, where $xiin (0,2)$ is the exponent characterizing the stripe of the kernel at the origin.
  arXiv  Detail & Related papers  (2020-06-17T09:59:18Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.