Optimal Orthogonal Group Synchronization and Rotation Group Synchronization

• URL: http://arxiv.org/abs/2109.13491v1
• Date: Tue, 28 Sep 2021 05:10:20 GMT
• Title: Optimal Orthogonal Group Synchronization and Rotation Group Synchronization
• Abstract summary: We analyze an iterative polar decomposition algorithm for the estimation of $Z*$. A matching minimax lower bound is established which leads to the optimality of the proposed algorithm.
• Score: 19.909352968029584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in\mathbb{R}^{d\times d}$ where $W_{ij}$ is a Gaussian random matrix and $Z_i^*$ is either an orthogonal matrix or a rotation matrix, and each $Y_{ij}$ is observed independently with probability $p$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $(1+o(1))\frac{\sigma^2 d(d-1)}{2np}$ when initialized by spectral methods. A matching minimax lower bound is further established which leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.

Related papers

• Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem [1.3537117504260623]
  We show a new class linking group theory, matrix analysis, and statistical estimation.<n>This problem does not appear in the standard catalogs of computational complexity.
  arXiv  Detail & Related papers  (2026-04-04T09:02:16Z)
• The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
  We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices.<n>An algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible.
  arXiv  Detail & Related papers  (2025-11-08T15:23:44Z)
• Robust random graph matching in Gaussian models via vector approximate message passing [0.0]
  We propose an efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n1-o(1)$ size.<n>Our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n1-o(1)$ size.
  arXiv  Detail & Related papers  (2024-12-21T03:15:38Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's algorithm for Streaming Principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm can achieve the minimax error bound under some regularity conditions in $O(d)$ space and $O(nd)$ time.
  arXiv  Detail & Related papers  (2024-02-11T16:36:48Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  We show that our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. In particular, our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. Our main algorithm can be viewed as a randomized block coordinate descent method.
  arXiv  Detail & Related papers  (2023-12-14T12:53:34Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  We show a proof to show DEAREST requires at most $mathcal O(+sqrtmnLvarepsilon-2)$ first-order oracle (IFO) calls and $mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$ communication rounds.
  arXiv  Detail & Related papers  (2022-10-25T11:37:11Z)
• 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)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles [12.005731086591139]
  Householder Dice (HD) is an algorithm for simulating dynamics on dense random matrix ensembles with translation-invariant properties. The memory and costs of the HD algorithm are $mathcalO(nT)$ and $mathcalO(nT2)$, respectively. Numerical results demonstrate the promise of the HD algorithm as a new computational tool in the study of high-dimensional random systems.
  arXiv  Detail & Related papers  (2021-01-19T04:50:53Z)
• SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
  We study the phase synchronization problem with noisy measurements $Y=z*z*+sigma WinmathbbCntimes ntimes n. We prove that SDP achieves error bound $ (1+o)fracnp22np$ under a squared $ell$ loss.
  arXiv  Detail & Related papers  (2021-01-07T03:14:05Z)
• 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)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

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.