Fast, Accurate and Memory-Efficient Partial Permutation Synchronization

• URL: http://arxiv.org/abs/2203.16505v2
• Date: Thu, 31 Mar 2022 14:14:52 GMT
• Title: Fast, Accurate and Memory-Efficient Partial Permutation Synchronization
• Authors: Shaohan Li, Yunpeng Shi, Gilad Lerman
• Abstract summary: We propose an improved algorithm, CEMP-Partial, for estimating the corruption levels of the observed partial permutations. We prove that under adversarial corruption, though without additive noise and with certain assumptions, CEMP-Partial is able to exactly classify corrupted and clean partial permutations. We demonstrate state-of-the-art accuracy, speed and memory efficiency of our method on both synthetic and real datasets.
• Score: 15.813217907813778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Previous partial permutation synchronization (PPS) algorithms, which are commonly used for multi-object matching, often involve computation-intensive and memory-demanding matrix operations. These operations become intractable for large scale structure-from-motion datasets. For pure permutation synchronization, the recent Cycle-Edge Message Passing (CEMP) framework suggests a memory-efficient and fast solution. Here we overcome the restriction of CEMP to compact groups and propose an improved algorithm, CEMP-Partial, for estimating the corruption levels of the observed partial permutations. It allows us to subsequently implement a nonconvex weighted projected power method without the need of spectral initialization. The resulting new PPS algorithm, MatchFAME (Fast, Accurate and Memory-Efficient Matching), only involves sparse matrix operations, and thus enjoys lower time and space complexities in comparison to previous PPS algorithms. We prove that under adversarial corruption, though without additive noise and with certain assumptions, CEMP-Partial is able to exactly classify corrupted and clean partial permutations. We demonstrate the state-of-the-art accuracy, speed and memory efficiency of our method on both synthetic and real datasets.

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)
• Fast OMP for Exact Recovery and Sparse Approximation [4.915061940934031]
  This paper advances Orthogonal Matching Pursuit (OMP) in two fronts. It offers a fast algorithm for the projection of the input signal at each iteration, and a new selection criterion for making the greedy choice. Experiment results show significant improvement over the classical OMP in computation time.
  arXiv  Detail & Related papers  (2024-03-29T20:39:37Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K. We express this algorithm within the setting of discrete Morse theory, which considerably reduces the number of input simplices to consider. We also introduce a stratification approach to the problem, that we call "sandwiching"
  arXiv  Detail & Related papers  (2022-06-27T10:54:24Z)
• Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering [18.888312436971187]
  This paper proposes a new SSC scheme using generalized OMP (GOMP) GOMP involves fewer iterations, thereby enjoying lower algorithmic complexity. The proposed stopping rule is free from off-line estimation of subspace dimension and noise power.
  arXiv  Detail & Related papers  (2022-04-06T04:20:35Z)
• Rethinking Space-Time Networks with Improved Memory Coverage for Efficient Video Object Segmentation [68.45737688496654]
  We establish correspondences directly between frames without re-encoding the mask features for every object. With the correspondences, every node in the current query frame is inferred by aggregating features from the past in an associative fashion. We validated that every memory node now has a chance to contribute, and experimentally showed that such diversified voting is beneficial to both memory efficiency and inference accuracy.
  arXiv  Detail & Related papers  (2021-06-09T16:50:57Z)
• Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory [0.0]
  We present a divide and conquer algorithm that computes the exact globally optimal DTW alignment using O(M+N) memory. Our algorithm can be parallelized up to a factor of min(M, N) with the same memory constraints, so it can still run more efficiently than the textbook version with an adequate GPU.
  arXiv  Detail & Related papers  (2020-08-04T15:00:33Z)
• Fast and Robust Iterative Closest Point [32.42799285301607]
  Iterative Closest Point (ICP) is a fundamental technique for rigid registration between two point sets. Recent work such as Sparse ICP achieves robustness via sparsity optimization at the cost of computational speed. We show that the classical point-to-point ICP can be treated as a majorization-minimization (MM) algorithm, and propose an Anderson acceleration approach to speed up its convergence.
  arXiv  Detail & Related papers  (2020-07-15T11:32:53Z)
• 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)

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.