Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fast, Accurate and Memory-Efficient Partial Permutation Synchronization   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.

14
The categories of this paper are: math-ph
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
33
The categories of this paper are: plasm-ph
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
23
The categories of this paper are: solv-int
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
10
The categories of this paper are: q-bio
13
The categories of this paper are: quant-ph
3
The categories of this paper are: physics
28
The categories of this paper are: alg-geom
19
The categories of this paper are: eess