Dynamic angular synchronization under smoothness constraints

• URL: http://arxiv.org/abs/2406.04071v1
• Date: Thu, 6 Jun 2024 13:36:41 GMT
• Title: Dynamic angular synchronization under smoothness constraints
• Authors: Ernesto Araya, Mihai Cucuringu, Hemant Tyagi,
• Abstract summary: We find non-asymptotic recovery guarantees for the mean-squared error (MSE) under different statistical models. We show that the MSE converges to zero as $T$ increases under milder conditions than in the static setting.
• Score: 9.196539011582361
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an undirected measurement graph $\mathcal{H} = ([n], \mathcal{E})$, the classical angular synchronization problem consists of recovering unknown angles $\theta_1^*,\dots,\theta_n^*$ from a collection of noisy pairwise measurements of the form $(\theta_i^* - \theta_j^*) \mod 2\pi$, for all $\{i,j\} \in \mathcal{E}$. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from pairwise comparisons. In this paper, we consider a dynamic version of this problem where the angles, and also the measurement graphs evolve over $T$ time points. Assuming a smoothness condition on the evolution of the latent angles, we derive three algorithms for joint estimation of the angles over all time points. Moreover, for one of the algorithms, we establish non-asymptotic recovery guarantees for the mean-squared error (MSE) under different statistical models. In particular, we show that the MSE converges to zero as $T$ increases under milder conditions than in the static setting. This includes the setting where the measurement graphs are highly sparse and disconnected, and also when the measurement noise is large and can potentially increase with $T$. We complement our theoretical results with experiments on synthetic data.

Related papers

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Self-Ensembling Gaussian Splatting for Few-shot Novel View Synthesis [55.561961365113554]
  3D Gaussian Splatting (3DGS) has demonstrated remarkable effectiveness for novel view synthesis (NVS) However, the 3DGS model tends to overfit when trained with sparse posed views, limiting its generalization capacity for broader pose variations. We introduce a self-ensembling Gaussian Splatting (SE-GS) approach to alleviate the overfitting problem.
  arXiv  Detail & Related papers  (2024-10-31T18:43:48Z)
• Joint Learning of Linear Dynamical Systems under Smoothness Constraints [5.2395896768723045]
  We consider the problem of joint learning of multiple linear dynamical systems. In particular, we show conditions under which the mean-squared error bounds on the mean-squared error (MSE) converges to zero as $m$ increases.
  arXiv  Detail & Related papers  (2024-06-03T08:29:42Z)
• The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime [0.0]
  Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation. We consider two types of (correlated) weighted complete graphs with edge weights given by $A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$.
  arXiv  Detail & Related papers  (2024-02-23T04:58:54Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• 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)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$. Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
  arXiv  Detail & Related papers  (2021-04-06T15:34:14Z)
• 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)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

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.