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
- 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) - Parsimonious Optimal Dynamic Partial Order Reduction [1.5029560229270196]
We present Parsimonious-OPtimal (POP) DPOR algorithm for analyzing multi-threaded programs under sequential consistency.
POP combines several novel techniques, including (i) a parsimonious race reversal strategy, which avoids multiple reversals of the same race, and (ii) an eager race reversal strategy to avoid storing initial fragments of to-be-explored executions.
Our implementation in Nidhugg shows that these techniques can significantly speed up the analysis of concurrent programs, and do so with low memory consumption.
arXiv Detail & Related papers (2024-05-18T00:07:26Z) - 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) - 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.