Message Passing Least Squares Framework and its Application to Rotation Synchronization

• URL: http://arxiv.org/abs/2007.13638v3
• Date: Sat, 15 Aug 2020 02:00:34 GMT
• Title: Message Passing Least Squares Framework and its Application to Rotation Synchronization
• Authors: Yunpeng Shi and Gilad Lerman
• Abstract summary: We first describe our theoretically guaranteed message passing algorithm that estimates the corruption levels of the measured group ratios. We then propose a novel reweighted least squares method to estimate the group elements, where the weights are iteratively updated using the estimated corruption levels. We demonstrate the superior performance of our algorithm over state-of-the-art methods for rotation synchronization using both synthetic and real data.
• Score: 16.650654530240566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an efficient algorithm for solving group synchronization under high levels of corruption and noise, while we focus on rotation synchronization. We first describe our recent theoretically guaranteed message passing algorithm that estimates the corruption levels of the measured group ratios. We then propose a novel reweighted least squares method to estimate the group elements, where the weights are initialized and iteratively updated using the estimated corruption levels. We demonstrate the superior performance of our algorithm over state-of-the-art methods for rotation synchronization using both synthetic and real data.

Related papers

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment. We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• A Novel Framework for Improving the Breakdown Point of Robust Regression Algorithms [1.9594639581421422]
  We present an effective framework for improving the breakdown point of robust regression algorithms. We derive a consistent robust regression algorithm with iterative local search (CORALS)
  arXiv  Detail & Related papers  (2023-05-20T15:59:33Z)
• Unrolled algorithms for group synchronization [7.969977930633441]
  Group synchronization problem involves estimating a collection of group elements from noisy measurements of their pairwise ratios. Standard methods to estimate the group elements are based on iteratively applying linear and non-linear operators. Motivated by the structural similarity to deep neural networks, we adopt the concept of algorithm unrolling.
  arXiv  Detail & Related papers  (2022-07-19T17:25:56Z)
• Robust Group Synchronization via Quadratic Programming [15.254598796939922]
  We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC) We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.
  arXiv  Detail & Related papers  (2022-06-17T20:08:03Z)
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization [20.413250472034143]
  We propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR) The proposed algorithm is efficient and scales linearly with the number of data points. We also leverage the recently developed leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships.
  arXiv  Detail & Related papers  (2021-12-25T07:38:14Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  In rank aggregation problems, users exhibit various accuracy levels when comparing pairs of items. We propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons. We prove that our algorithm can return the true ranking of items with high probability.
  arXiv  Detail & Related papers  (2021-10-08T13:51:55Z)
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods [0.7614628596146599]
  Group synchronization asks to recover group elements from their pairwise measurements. spectral methods have enjoyed great popularity due to their efficiency and convenience. For permutation group synchronization under random corruption, we show that the widely-used two-step procedure can recover all the group elements exactly.
  arXiv  Detail & Related papers  (2020-08-12T14:20:16Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  We consider the problem of optimizing an unknown (typically non-producing) function with a bounded norm. We introduce an algorithm based on Fast-Slow GP-UCB based on "fast but non-robust" and "slow" We argue that certain dependencies cannot be required depending on the corruption level.
  arXiv  Detail & Related papers  (2020-03-04T09:46:58Z)

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.