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
- 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) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - 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) - An extension of the angular synchronization problem to the heterogeneous
setting [8.391320712953553]
We find a generalization to the setting where there exist $k$ unknown groups of angles $theta_l,1, dots,theta_l,n$, for $l=1,dots,k$.
This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from preference relationships.
arXiv Detail & Related papers (2020-12-29T20:29:10Z) - 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.