Near-Optimal Joint Object Matching via Convex Relaxation

Introduction

Finding consistent relations across multiple objects is a fundamental scientific problem spanning many fields. A partial list includes jigsaw puzzle solving , structure from motion , re-assembly of fragmented objects and documents , and DNA/RNA shotgun assembly sequencing . Compared with the rich literature in pairwise matching (e.g. of graphs, images or shapes), joint matching of multiple objects has not been well explored. A naive approach for joint object matching is to pick a base object and perform pairwise matching with each of the remaining objects. However, as pairwise matching algorithms typically generate noisy results, the performance of such approaches is often far from satisfactory in practice. This gives rise to the question as to how to aggregate and exploit information from all pairwise maps that one computes, in order to improve joint object matching in a consistent and efficient manner.

In this paper, we represent each object as a discrete set of points or elements, and investigate the problem of joint matching over $n$ different sets, for which the input / observation is a collection of pairwise maps computed in isolation. A natural and popular criterion to preserve the global relational compatibility is called cycle-consistency, i.e., that composition of maps between two objects should be independent of the connecting path chosen. Such criterion has recently been invoked in many algorithms to detect outliers among the pairwise input maps. These works have shown experimentally that one can use inconsistent cycles to prune outliers, provided that the corruption rate is sufficiently small.

Despite the empirical advances of these works, little is known on the theoretical side, namely, under what conditions can the underlying ground-truth maps be reliably recovered. Recent work by provided the first theoretical guarantee for robust and consistent joint matching. However, there are several fundamental issues left unaddressed that must be faced in order to accommodate practical challenges.

Dense Input Errors: The state-of-the-art results (e.g. ) did not provide theoretical support when more than 50% of the input matches are corrupted. This gives rise to the question regarding their applicability in the presence of highly noisy sources, in which case the majority of the input maps can be corrupted. Observe that as the number $n$ of objects to be matched increases, the amount of pairwise maps one can obtain significantly exceeds $n$. As a result, dense error correction is information theoretically possible as long as the global consistency across pairwise maps can be appropriately exploited. While one would expect an ideal algorithm to work even when most input maps are random outliers, the challenge remains as to whether there exist computationally feasible methods that can provably detect and separate dense outliers.

Partial Similarity: To the best of our knowledge, all prior approaches dealt only with a restricted scenario where the ground-truth maps are given by full isomorphisms (i.e. one-to-one correspondences between any two sets). In reality, a collection of objects usually exhibit only partial similarity, as in the case of images of the same scene but from different camera positions. These practical scenarios require consistent matching of multiple objects that are only partially similar to each other.

Incomplete Input Maps: Computing pairwise maps across all object pairs are often expensive, sometimes inadmissible, and in fact unnecessary. Depending on the characteristics of input sources, one might be able to infer unobserved maps from a small sample of noisy pairwise matches. While considered incomplete inputs, the tradeoff between the undersampling factor and the error-correction ability remains unknown.

All in all, practical applications require matching partially similar objects from a small fraction of densely corrupted pairwise maps — a goal this paper aims to achieve.

This paper is concerned with joint object matching under dense input errors. Our main contributions in this regard are three-fold.

Algorithms: Inspired by the recent evidence on the power of convex relaxation, we propose to solve the joint matching problem via a semidefinite program called MatchLift. The algorithm relaxes the binary-value constraints, and attempts to maximize the compatibility between the input and the recovered maps. The program is established upon a semidefinite conic constraint that relies on the total number $m$ of distinct elements to be matched. To this end, we propose to pre-estimate $m$ via a spectral method. Our methodology is essentially parameter free, and can be solved by scalable optimization algorithms.

Theory: We derive performance guarantees for exact matching. Somewhat surprisingly, MatchLift admits perfect map recovery even in the presence of dense input corruptions. Our findings reveal the near-optimal error-correction ability of MatchLift, i.e. as $n$ grows, the algorithm is guaranteed to work even when a dominant fraction – more precisely, a fraction $1-\Omega\left(\frac{\log^{2}n}{\sqrt{n}}\right)$ – of the inputs behave as random outliers. Besides, while the presence of partial similarity unavoidably incurs more severe types of input errors, MatchLift exhibits a strong recovery ability nearly order-wise equivalent to that in the full-similarity scenario, as long as the fraction of each object being disclosed is bounded away from zero. Finally, in many situations, MatchLift succeeds even with minimal input complexity, in the sense that it can reliably fill in all unobserved maps based on very few noisy partial inputs, as soon as the provided maps form a connected graph. This is information theoretically optimal.

Practice: We have evaluated the performance of MatchLift on several benchmark datasets. These datasets include several synthetic examples as well as real examples from several popular benchmarks. Experimental results on synthetic examples corroborate our theoretical findings. On real datasets, the quality of the maps generated by MatchLift outperforms the state-of-the-art object matching and graph clustering algorithms.

2 Prior Art

There has been numerous work studying the problem of object matching, either in terms of shape mapping, graph matching, or image mapping, which is impossible to enumerate. We list below a small sample of development on joint object matching, as well as its relation and distinction to the well-renowned graph clustering problem.

Object Matching. Early work on object matching focused primarily on matching pairs of objects in isolation (e.g. ). Due to the limited and biased information present in an isolated object pair, pairwise matching techniques can easily, sometimes unavoidably, generate false correspondences. Last few years have witnessed a flurry of activity in joint object matching, e.g. , which exploited the global cycle-consistency criterion to prune noisy maps. The fundamental understanding has recently been advanced by . Nevertheless, none of the prior work have demonstrated provable recovery ability when the majority of input maps/correspondences are outliers, nor were they able to accommodate practical scenarios where different objects only exhibit partial similarity. Recent work employed spectral methods for denoising in the full-similarity case. However, the errors considered therein are modeled as Gaussian-Wigner additive noise, which is not applicable in our setting. Another line of work proposed to recover global rigid transform between points via convex relaxation, where the point coordinates might only be partially observed. While this line of work is relevant, the problem considered therein is more specialized than the point-based joint matching studied in this paper; also, none of these paradigms are able to enable dense error correction.

Matrix Completion and Robust PCA. In a broader sense, our approach is inspired by the pioneering work in low-rank matrix completion and robust principal component analysis , which reveal the power of convex relaxation in recovering low-dimensional structures among high-dimensional objects. In fact, the ground truth herein is equivalent to a block-constant low-rank matrix , as occurred in various graph-related problems. Nevertheless, their theoretical analyses fail to provide tight bounds in our setting, as the low-rank matrix relevant in our cases is highly sparse as well. That said, additional structural assumptions need to be incorporated in order to achieve optimal performance.

Graph Clustering. The joint matching problem can be treated as a structured graph clustering (GC) problem, where graph nodes represent points on objects and the edge set encodes all correspondences. In this regard, any GC algorithm provides a heuristic to estimate graph matching. Nevertheless, there are several intrinsic structural properties herein that are not explored by any generic GC approaches. First, our input takes a block-matrix form, where each block is highly structured (i.e. doubly-substochastic), sparse, and inter-dependent. Second, the points belonging to the same object are mutually exclusive to each other. Third, the corruption rate for different entries can be highly non-symmetric – when translated into GC languages, this means that in-cluster edges might suffer from an order-of-magnitude larger error rate than inter-cluster edges. As a result, the findings for generic GC methods do not deliver encouraging guarantees when applied to our setting. Detailed theoretical and empirical comparisons are provided in Sections LABEL:sec:Theoretic-Guarantees and LABEL:sec:results, respectively.

3 Organization

The rest of the paper is organized as follows. Section LABEL:sec:Problem-Formulation formally presents the problem setup, including the input model and the expected output. Our two-step recovery procedure – a spectral method followed by a convex program called MatchLift – is described in Section LABEL:sec:Methodology. A scalable alternating direction method of multipliers (ADMM) together with a greedy rounding strategy is also introduced in Section LABEL:sec:Methodology. Section LABEL:sec:Theoretic-Guarantees presents the main theoretical performance guarantees for our method under a natural randomized model. All proofs of the main theorems are deferred to the appendices. We introduce numerical experiments demonstrating the practicability of our method in Section LABEL:sec:results, as well as empirical comparison with other best-known algorithms. Finally, Section LABEL:sec:Conclusions concludes the paper with a summary of our findings.

Problem Formulation and Preliminarieslabelsec:Problem-Formulation

This section presents the problem setup for matching multiple partially similar objects, and introduces an algebraic form for representing a collection of pairwise maps.

Below we formally define several important notions that will be used throughout this paper.

Set. We represent objects to be matched as discrete sets. For example, these sets can represent the vertex sets in the graph matching problem, or encode feature points when matching images.

Partial Map. Given two discrete sets $\mathcal{S}$ and $\mathcal{S}^{\prime}$, a subset $\phi\subset\mathcal{S}\times\mathcal{S}^{\prime}$ is termed a partial map if each element of $\mathcal{S}$ (resp. $\mathcal{S}^{\prime}$) is paired with at most one element of $\mathcal{S}^{\prime}$ (resp. $\mathcal{S}$) — in particular, not all elements need to be paired.

Map Graph. A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is called a map graph w.r.t. $n$ sets $\mathcal{S}_{1},\cdots,\mathcal{S}_{n}$ if (i) $\mathcal{V}:=\left\{\mathcal{S}_{1},\cdots,\mathcal{S}_{n}\right\}$, and (ii) $(\mathcal{S}_{i},\mathcal{S}_{j})\in\mathcal{E}$ implies that pairwise estimates on the partial maps $\phi_{ij}$ and $\phi_{ji}$ between $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$ are available.

2 Input and Output

The input and expected output for the joint object matching problem are described as follows.

Input (Noisy Pairwise Maps). Given $n$ sets $\mathcal{S}_{1},\cdots,\mathcal{S}_{n}$ with respective cardinality $m_{1},\cdots,m_{n}$ and a (possibly sparse) map graph $\mathcal{G}$, the input to the recovery algorithm consists of partial maps $\phi_{ij}^{\textup{in}}\text{ }\left((i,j)\in\mathcal{G}\right)$ between $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$ estimated in isolation, using any off-the-shelf pairwise matching method. Note that the input maps $\phi_{ij}^{\textup{in}}$ one obtain might not agree, partially or totally, with the ground truth.

Output (Consistent Global Matching). The main objective of this paper is to detect and prune incorrect pairwise input maps in an efficient and reliable manner. Specifically, we aim at proposing a tractable algorithm that returns a full collection of partial maps $\left\{\phi_{ij}\mid 1\leq i,j\leq n\right\}$ that are (i) globally consistent, and (ii) close to the provided pairwise maps – and under some conditions provably the ground-truth maps.

As will be detailed later, the key idea of our approach is to explore global consistency across all pairwise maps. In fact, points across different objects must form several clusters, and the ground-truth maps only exhibit in-cluster edges. We will introduce a novel convex relaxation tailored to the structure of the input maps (Section LABEL:sec:Methodology) and investigate its theoretical performance (Section LABEL:sec:Theoretic-Guarantees).

3 Joint Matching in Matrix Form

In the same spirit as most convex relaxation techniques (e.g., ), we use matrices to encode maps between objects. Specifically, we encode a partial map $\phi_{ij}:\mathcal{S}_{i}\mapsto\mathcal{S}_{j}$ as a binary matrix $\boldsymbol{X}_{ij}\in\{0,1\}^{|\mathcal{S}_{i}|\times|\mathcal{S}_{j}|}$ such that $\boldsymbol{X}_{ij}(s,s^{\prime})=1$ iff $(s,s^{\prime})\in\phi_{ij}$. Valid partial map matrices $\boldsymbol{X}_{ij}$ shall satisfy the following doubly sub-stochastic constraints:

We then use an $n\times n$ block matrix $\boldsymbol{X}\in\{0,1\}^{N\times N}$ to encode the entire collection of partial maps $\left\{\phi_{ij}\mid 1\leq i,j\leq n\right\}$ over $\left\{\mathcal{S}_{1},\cdots,\mathcal{S}_{n}\right\}$:

where $m_{i}:=\left|\mathcal{S}_{i}\right|$ and $N:=\sum_{i=1}^{n}m_{i}$. Note that all diagonal blocks are identity matrices, as each object is isomorphic to itself.

Methodologylabelsec:Methodology

This section presents a novel methodology, based on a theoretically rigorous and numerically efficient framework.

We start by discussing the consistency constraint on the underlying ground-truth maps. Assume that there exists a universe $\mathcal{S}=\{1,\cdots,m\}$ of $m$ elements such that i) each object $\mathcal{S}_{i}$ is a (partial) image of $\mathcal{S}$; ii) each element in $\mathcal{S}$ is contained in at least one object $\mathcal{S}_{i}$. Then the ground-truth correspondences shall connect points across objects that are associated with the same element.

Formally speaking, let the binary matrix $\boldsymbol{Y}_{i}\in\{0,1\}^{m_{i}\times m}$ encode the underlying correspondences between each point and the universe, i.e. for any $s_{i}\in\mathcal{S}_{i}$ and $s\in\mathcal{S}$,

with $\boldsymbol{Y}=(\boldsymbol{Y}_{1}^{\top},\cdots,\boldsymbol{Y}{}_{n}^{\top})^{\top}$, which makes clear that

This is equivalent to the graph partitioning setting with $m$ cliques. Consequently, a natural candidate is to seek a low-rank and positive semidefinite (PSD) matrix to approximate the input. However, this strategy does not effectively explore the sparsity structure underlying the map collection.

To obtain a more powerful formulation, the proposed algorithm is based on the observation that even under dense input corruption, we are often able to obtain reliable estimates on $m$ – the universe size, using spectral techniques. This motivates us to incorporate the information of $m$ into the formulation so as to develop tighter relaxation. Specifically, we lift $\boldsymbol{X}$ with one more dimension and consider

which is strictly tighter than merely imposing $\boldsymbol{X}\succeq{\bf 0}$. Intuitively, the formulation (LABEL:eq:X_rank_PSD) entitles us one extra degree of freedom to assist in outlier pruning, which turns out to be crucial in “debiasing” the errors. Encouragingly, this tightened constraint leads to remarkably improved theoretical guarantees, as will be shown in Section LABEL:sec:Theoretic-Guarantees. In the following, we formally present our two-step matching procedure.

With this trimming procedure, we propose to pre-estimate $m$ via Algorithm LABEL:alg:EsimateM.

Step II: Map Recovery. Now that we have obtained an estimate on $m$, we are in position to present our optimization heuristic that exploits the structural property (LABEL:eq:X_rank_PSD). In order to guarantee that the recovery is close to the provided maps $\phi_{ij}^{\textup{in}}$, one alternative is to maximize correspondence agreement (i.e. the number of compatible non-zero entries) between the input and output. This results in an objective function:

Since searching over all 0-1 map matrices is intractable, we propose to relax the binary constraints. Putting these together leads to the following semidefinite program referred to as MatchLift:

Here, $\lambda$ represents the regularization parameter that balances the compatibility to the input and the sparsity structure. As we will show, the recovery ability of MatchLift is not sensitive to the choice of $\lambda$. By default, one can set

which results in a parameter-free formulation.

Careful readers will note that the set of doubly stochastic constraints (LABEL:eq:substochastic) can be further added into the program. Nevertheless, while enforcement of these constraints (LABEL:eq:substochastic) results in a strictly tighter relaxation, it only leads to marginal improvement when (LABEL:eq:SDP_conic) is present. As a result, we remove them for the sake of computational efficiency. We note, however, that in the scenario where $m$ is difficulty to estimate, imposing (LABEL:eq:substochastic) will “become crucial in allowing a constant fraction (e.g. 50%) of error rate, although dense error correction might not be guaranteed.

This algorithm, all at once, attempts to disentangle the ground truth and outliers as well as predict unobserved maps via convex relaxation, inspired by recent success in sparse and low-rank matrix decomposition . Since the ground truth matrix is simultaneously low-rank and sparse; existing methodologies, which focus on dense low-rank matrices, typically yield loose, uninformative bounds in our setting.

Finally, we note that our matching algorithm and main results are well suited for a broad class of scenarios where each pairwise input can be modeled as a (partial) permutation matrix. For instance, our setting subsumes phase correlation , angular synchronization , and multi-signal alignment as special cases.

2 Alternating Direction Methods of Multipliers (ADMM)labelsub:ADMM

Most advanced off-the-shelf SDP solvers like SeDuMi or MOSEK are typically based on interior point methods, and such second-order methods are unable to handle problems with large dimensionality. For practical applicability, we propose a first-order optimization algorithm for approximately solving MatchLift, which is a variant of the ADMM method for semidefinite programs presented in . Theoretically it is guaranteed to converge. Empirically, it is often the case that ADMM converges to modest accuracy within a reasonable amount of time, and produces desired results with the assistance of appropriate rounding procedures. This feature makes ADMM practically appealing in our case since the ground-truth matrix is known to be a 0-1 matrix, for which moderate entry-wise precision is sufficient to ensure good rounding accuracy. The details of the ADMM algorithm are deferred to Appendix LABEL:sec:ADMM-Appendix.

3 Rounding Strategylabelsub:Rounding

As MatchLift solves a relaxed program of the original convex problem, it may return fractional solutions. In this case, we propose a greedy rounding method to generate valid partial maps. Given the solution $\hat{\boldsymbol{X}}$ to MatchLift, the proposed strategy proceeds as in Algorithm LABEL:alg:Rounding. One can verify that this simple deterministic rounding strategy returns a matrix that encodes a consistent collection of partial maps. Note that $\boldsymbol{v}_{i}^{T}$ denotes the $i$th row of a matrix $\boldsymbol{V}$.

Theoretical Guarantees: Exact Recoverylabelsec:Theoretic-Guarantees

Our heuristic algorithm MatchLift recovers, under a natural randomized setting, the ground-truth maps even when only a vanishing portion of the input correspondences are correct. Furthermore, MatchLift succeeds with minimal input complexity, namely, the algorithm is guaranteed to work as soon as those input maps that coincide with the ground truth maps form a connected map graph.

In the following, we present a natural randomized model, under which the feature of MatchLift is easiest to interpret. Specifically, consider a universe $[m]:=\left\{1,2,\cdots,m\right\}$. The randomized setting consider herein is generated through the following procedure.

The above mean condition (LABEL:eq:MeanOutlier) holds, for example, when the augmented block (i.e. that obtained by enhancing $\mathcal{S}_{i}$ and $\mathcal{S}_{j}$ to have all $m$ elements) is drawn from the entire set of permutation matrices or other symmetric groups uniformly at random. While we impose (LABEL:eq:MeanOutlier) primarily to simplify our presentation of the analysis, we remark that this assumption can be significantly relaxed without degrading the matching performance.

We also note that the outliers do not need to be generated in an i.i.d. fashion. Our main results hold as long as they are jointly independent and satisfy the mean condition (LABEL:eq:MeanOutlier).

2 Main Theorem: Near-Optimal Matchinglabelsub:Main-Theorem

We are now in position to state our main results, which provide theoretical performance guarantees for our algorithms.

labelthm:SpectralMethodConsider the above randomized model. There exists an absolute constant $c_{1}>0$ such that with probability exceeding $1-\frac{1}{m^{5}n^{5}}$, the estimate on $m$ returned by Algorithm LABEL:alg:EsimateM is exact as long as

See Appendix LABEL:sec:Proof_thm:SpectralMethod-m.∎

Theorem LABEL:thm:SpectralMethod ensures that one can obtain perfect estimate on the universe size or, equivalently, the rank of the ground truth map matrix via spectral methods. With accurate information on $m$, MatchLift allows perfect matching from densely corrupted inputs, as revealed below.

labelthm:RandomGraph-1Consider the randomized model described above. There exist universal constants $c_{0},c_{1},c_{2}>0$ such that for any

then the solution to MatchLift is exact and unique with probability exceeding $1-\left(mn\right)^{-3}$.

See Appendix LABEL:sec:Proof-of-Theorem-RandomGraph.∎

Near-Optimal Recovery under Dense Errors. Under the randomized model, MatchLift succeeds in pruning all outliers and recovering the ground truth with high probability. Somewhat surprisingly, this is guaranteed to work even when the non-corrupted pairwise maps account for only a vanishing fraction of the inputs. As a result, MatchLift achieves near-optimal recovery performance in the sense that as the number $n$ of objects grows, its outlier-tolerance rate can be arbitrarily close to $1$. Equivalently speaking, in the asymptotic regime, almost all input maps – more precisely, a fraction

of inputs – can be badly corrupted by random errors without degrading the matching accuracy. This in turn highlights the significance of joint object matching: no matter how noisy the input sources are, perfect matching can be obtained as long as sufficiently many instances are available.

To the best of our knowledge, none of the prior results can support perfect recovery with more than 50% corruptions, regardless of how large $n$ can be. The only comparative performance is reported for the robust PCA setting, where semidefinite relaxation enables dense error correction . However, their condition cannot be satisfied in our case. Experimentally, applying RPCA on joint matching is unable to tolerate dense errors (see Section LABEL:sec:results).

3 Comparison with Prior Approacheslabelsub:Comparison-Prior-Approaches

Our exact recovery condition significantly outperforms the best-known performance guarantees, including various SDP heuristics for matching problems, as well as general graph clustering approaches when applied to object matching, detailed below.

Experimental Evaluation

In this section, we evaluate the performance of MatchLift and compare it against and other graph matching methods. We consider both synthetic examples, which are used to verify the exact recovery conditions described above, as well as popular benchmark datasets for evaluating the practicability on real-world images.

In comparison, Figure LABEL:Fig:PT(b) and Figure LABEL:Fig:PT(d) illustrate the phase transition diagrams achieved by the algorithm proposed in . One can see that MatchLift is empirically superior, as is unable to allow dense error correction in our case.

2 Real-World Examples

We have applied our algorithm on six benchmark datasets, i.e., CMU-House, CMU-Hotel, two datasets (Graf and Bikes) from available online: robots.ox.ac.uk/ vgg/research/affine and two new datasets (referred as Chair and Building, respectively) designed for evaluating joint partial object matching. As shown in Figures LABEL:Fig:Benchmark-building and LABEL:Fig:Benchmark-chair, the Building data set contains $16$ images taken around a building , while the Chair data set contains $16$ images of a chair model from different viewpoints. In the following, we first discuss the procedure for generating the input to our algorithm, i.e., the input sets and the initial maps. We then present the evaluation setup and analyze the results.

Feature points and initial maps. To make fair comparisons with previous techniques on CMU-House and CMU-Hotel, we use the features points provided in and apply the spectral matching algorithm described in to establish initial maps between features points. To assess the performance of the proposed algorithm with sparse input maps, we only match each image with $10$ random neighboring images.

To handle raw images in Chair, Building, Graf and Bikes, we apply a different strategy to build feature points and initial maps. We first detect dense SIFT feature points on each image. We then apply RANSAC to obtain correspondences between each pair of images. As SIFT feature points are over-complete, many of them do not appear in the resulting feature correspondences between pairs of views. Thus, we remove all feature points that have less than $2$ appearances in all pair-wise maps. We further apply farthest point sampling on the feature points until the sampling density is above $0.05w$, where $w$ is the width of the input images. The remaining feature points turn out to be much more distinct and thus are suitable for joint matching (See Figure LABEL:Fig:Downsampling). For the experiments we have tested, we obtain about $60-100$ features points per image.

Evaluation protocol. On CMU-House and CMU-Hotel, we count the percentage of correct feature correspondences produced by each algorithm. On Chair, Building, Graf and Bikes, we apply the metric described in , which evaluates the deviations of manual feature correspondences. As the feature points computed on each image do not necessarily align with the manual features, we apply to interpolate feature level correspondences into pixel-wise correspondences for evaluation.

Results. Table LABEL:Table:CMU shows the results of various algorithms on CMU-House and CMU-Hotel. We can see that even with moderate initial maps, MatchLift recovers all ground-truth correspondences. In contrast, the method of can only recover $92.2\%$ and $90.1\%$ ground-truth correspondences on CMU-House and CMU-Hotel, respectively. Note that, MatchLift also outperforms state-of-the-art learning based graph matching algorithms . This shows the the advantage of joint object matching.

Figure LABEL:Fig:Comparison-CMU and Figure LABEL:Fig:Benchmark1 illustrate the results of MatchLift on Chair, Building, Graf and Bikes. As these images contain noisy background information, the quality of the input maps is lower than those on House and Hotel. Encouragingly, MatchLift still recovers almost all manual correspondences. Moreover, MatchLift significantly outperforms , as the fault-tolerance rate of is limited by a small constant barrier.

Another interesting observation is that the improvements on Graf and Bikes (each has 6 images) are lower than those on Chair and Building (each has 16 images). This is consistent with the common knowledge of data-driven effect, where large object collections possess stronger self-correction power than small object collections.

Conclusionslabelsec:Conclusions

This paper delivers some encouraging news: given a few noisy object matches computed in isolation, a collection of partially similar objects can be accurately matched via semidefinite relaxation – an approach which provably works under dense errors. The proposed algorithm is essentially parameter-free, and can be solved by ADMM achieving remarkable efficiency and accuracy, with the assistance of a greedy rounding strategy.

The proposed algorithm achieves near-optimal error-correction ability, as it is guaranteed to work even when a dominant fraction of inputs are corrupted. This in turn underscore the importance of joint object matching: however low the quality of input sources is, perfect matching is achievable as long as we obtain sufficiently many instances. Also, while partial matching may incur much more severe input errors than those occurring in full-similarity matching, in many situations, the recovery ability of our algorithm is nearly the same as that in the full-similarity case (up to some constant factor). In a broader sense, our findings suggest that a large class of combinatorial / integer programming problems might be solved perfectly by semidefinite relaxation.

Appendix A Alternating Direction Method of Multipliers (ADMM)labelsec:ADMM-Appendix

This section presents the procedure for the ADMM algorithm. For notational simplicity, we represent the convex program as follows:

where we denote \overline{\boldsymbol{X}}:=\left[\begin{array}[]{cc}m&{\bf 1}^{\top}\\ {\bf 1}&\boldsymbol{X}\end{array}\right]. The matrices and operators are defined as follows

(i) $\boldsymbol{W}$ encapsulate all block coefficient matrices $\boldsymbol{W}_{ij}$ for all $(i,j)\in\mathcal{G}$;

(ii) $\mathcal{A}(\overline{\boldsymbol{X}})=\boldsymbol{b}$ represents the constraint that $\boldsymbol{X}_{ii}=\boldsymbol{I}_{m_{i}}$ ($1\leq i\leq n$) and the constraint \overline{\boldsymbol{X}}=\left[\begin{array}[]{cc}m&{\bf 1}^{\top}\\ {\bf 1}&\boldsymbol{X}\end{array}\right];

(iii) The variables on the right hand, i.e., $\boldsymbol{y}_{\mathcal{A}},\boldsymbol{Z}$ and $\boldsymbol{S}$, represent dual variables associated with respective constraints.

The Lagrangian associated with the convex program can be given as follows

where $\mathcal{A}^{*}$ denotes the conjugate operator w.r.t. an operator $\mathcal{A}$. The augmented Lagrangian for the convex program can now be written as

Appendix B Proof of Theorem LABEL:thm:SpectralMethodlabelsec:Proof_thm:SpectralMethod-m

The key step to the proof of Theorem LABEL:thm:SpectralMethod is to show that the set of outliers, even when they account for a dominant portion of the input matrix, behave only as a small perturbation to the spectrum of the non-corrupted components. Under the randomized model described in Section LABEL:sub:Randomized-Model, it can be easily seen that the trimming procedure is not invoked with high probability. Consequently, Theorem LABEL:thm:SpectralMethod can be established through the following lemma.

Generate a symmetric block matrix $\boldsymbol{A}=\left[\boldsymbol{A}_{ij}\right]_{1\leq i,j\leq n}$ such that

$\boldsymbol{M}$ is a principal minor of $\boldsymbol{A}$ from rows / columns at indices from a set $I\subseteq\left\{1,2,\cdots,mn\right\}$, where each $1\leq i\leq mn$ is contained in $I$ independently with probability $q$.

Then there exist absolute constants $c_{1},c_{2}>0$ such that if $p\geq c_{1}\frac{\log^{2}\left(mn\right)}{q\sqrt{\tau n}}$, one has

with probability exceeding $1-\frac{1}{m^{5}n^{5}}$. Here, $\lambda_{i}(\boldsymbol{M})$ represents the $i$th largest eigenvalue of $\boldsymbol{M}$.

Without loss of generality, we assume that $\boldsymbol{P}_{i}=\boldsymbol{I}_{m}$ for all $1\leq i\leq n$, since rearranging rows / columns of $\boldsymbol{A}$ does not change its eigenvalues. For convenience of presentation, we write $\boldsymbol{A}=\boldsymbol{Y}+\boldsymbol{Z}$ such that

Apparently, $\boldsymbol{Z}$ is a block diagonal matrix satisfying

which is only a mild perturbation of $\boldsymbol{Y}$. This way we have reduced to the case where all blocks (including diagonal blocks) are i.i.d., which is slightly more convenient to analyze.

Here, $n_{i}$ ($1\leq i\leq m$) denotes the cardinality of a set $I_{i}$ generated by independently sampling $n$ elements each with probability $q$, and we set $N:=n_{1}+\cdots+n_{m}$ for simplicity. From Bernstein inequality, there exist universal constants $c_{5},c_{6}>0$ such that if $q>\frac{c_{5}\log\left(mn\right)}{n}$, then

holds with probability exceeding $1-\left(mn\right)^{-10}$.

which satisfies $\left|\Delta_{N}\right|\leq m\max_{1\leq i\leq m}\left|\Delta_{i}\right|$.

By Schur complement condition for positive definite matrices , if \left[\begin{array}[]{cc}\boldsymbol{C}&\boldsymbol{B}\\ \boldsymbol{B}^{\top}&\boldsymbol{D}\end{array}\right]\succ{\bf 0}, then $\boldsymbol{C}\succ{\bf 0}$ and $\boldsymbol{D}-\boldsymbol{B}^{\top}\boldsymbol{C}^{-1}\boldsymbol{B}\succ{\bf 0}$. Applying this condition to $\overline{\boldsymbol{Y}}_{I,0}$ suggests that $\overline{\boldsymbol{Y}}_{I,0}\succ{\bf 0}$ can only hold when

which however cannot be satisfied since $\left(1-p\right)-\frac{p\left(1-p\right)}{m}\frac{1}{p}{\bf 1}_{m}^{\top}\cdot{\bf 1}_{m}=0$. Thus, $\overline{\boldsymbol{Y}}_{I,0}$ is rank deficient.

In fact, all non-zero eigenvalues of $\overline{\boldsymbol{Y}}_{I,0}$ can be quantified as well. Specifically, for any vector

That said, $\tau qpn$ is an eigenvalue of $\overline{\boldsymbol{Y}}_{I,0}$ with multiplicity $m-1$. On the other hand, we have

indicating that $\tau qn$ is another eigenvalue of $\overline{\boldsymbol{Y}}_{I,0}$. Putting these together yields

Furthermore, the residual component $\overline{\boldsymbol{Y}}_{I,\Delta}$ can be bounded as follows

where the last inequality follows from (LABEL:eq:Concentration-ni). This taken collectively with (LABEL:eq:Yi_mean_decomposition) and (LABEL:eq:evalue_Yi0) yields that: when $p>\frac{2c_{6}\log^{2}\left(mn\right)}{\sqrt{nq}}$ or, equivalently, when $2c_{6}\sqrt{nq\log\left(mn\right)}<\frac{1}{\log^{1.5}\left(mn\right)}npq$, one has

Finally, the claim follows by substituting (LABEL:eq:EvalueYiMeanBound) and (LABEL:eq:Yvar_UB) into (LABEL:eq:Evalue-M-LB) and (LABEL:eq:Evalue-M-UB).∎

Appendix C Proof of Theorem LABEL:thm:RandomGraph-1 labelsec:Proof-of-Theorem-RandomGraph

To prove Theorem LABEL:thm:RandomGraph-1, we first analyze the Karush–Kuhn–Tucker (KKT) condition for exact recovery, which provides a sufficient and almost necessary condition for uniqueness and optimality. Valid dual certificates are then constructed to guarantee exact recovery.

Furthermore, we define a vector $\boldsymbol{d}$ to be

In fact, when $n_{i}$’s are sufficiently close to each other, $\boldsymbol{d}\cdot\boldsymbol{d}^{\top}$ is a good approximation of ${\bf 1}\cdot{\bf 1}^{\top}$, as claimed in the following lemma.

labellemma:MeanApproxConsider a set of Bernoulli random variables $\nu_{i}\sim\text{Bernoulli}\left(p\right)$ ($1\leq i\leq n$), and set $s:=\sum_{i=1}^{n}\nu_{i}$. Let $n_{i}$ ($1\leq i\leq m$) be independent copies of $s$, and denote $N=n_{1}+\cdots+n_{m}$. If $p>\frac{c_{7}\log^{2}\left(mn\right)}{n}$, then the matrix

with probability exceeding $1-\frac{1}{m^{5}n^{5}}$, where $c_{7},c_{8},c_{9}$ are some universal constants.

See Appendix LABEL:sec:Proof_lemma:SpectralGapTight-1.∎

Since $p^{2}\boldsymbol{d}\cdot\boldsymbol{d}^{\top}$ is equivalent to $\boldsymbol{A}$ defined in (LABEL:eq:DefnA) up to row / column permutation, Lemma LABEL:lemma:MeanApprox reveals that

The following bound on the operator norm of a random block matrix is useful for deriving our main results.

labellemma:MomentMethodLet $\boldsymbol{M}=\left[\boldsymbol{M}_{ij}\right]_{1\leq i,j\leq n}$ be a symmetric block matrix, where $\boldsymbol{M}_{ij}$’s are jointly independent $m_{i}\times m_{j}$ matrices satisfying

Besides, $m_{i}\leq m$ holds for all $1\leq i\leq n$. Then there exists an absolute constant $c_{0}>0$ such that

holds with probability exceeding $1-\frac{1}{m^{5}n^{5}}$.

See Appendix LABEL:sec:Proof_lemma:MomentMethod.∎

Additionally, the second smallest eigenvalue of the Laplacian matrix of a random Erdős–Rényi graph can be bounded below by the following lemma.

with probability exceeding $1-\frac{2}{(mn)^{5}}$.

See Appendix LABEL:sec:Proof_lemma:SpectralGapTight.∎

Finally, if we denote by $n_{s}$ (resp. $n_{s,t}$) the number of sets $\mathcal{S}_{i}$ ($1\leq i\leq n$) containing the element $s$ (resp. containing $s$ and $t$ simultaneously), then these quantities sharply concentrate around their mean values, as stated in the following lemma.

hold with probability exceeding $1-\frac{1}{(mn)^{10}}$.

In passing, the claim follows immediately from the Bernstein inequality that

where $\nu_{i}\sim\text{Bernoulli}(p)$ are i.i.d. random variables. Interested readers are referred to for a tutorial.∎

C.2 Optimality and Uniqueness Conditionlabelsec:Duality

Recall that $n_{i}:=\left|\mathcal{I}_{i}\right|$ denotes the number of sets $\mathcal{S}_{j}$ containing the element $i$. The convex relaxation is exact if one can construct valid dual certificates, as summarized in the following lemma.

That said, to prove Theorem LABEL:thm:RandomGraph-1, it is sufficient (under the hypotheses of Theorem LABEL:thm:RandomGraph-1) to generate, with high probability, valid dual certificates $\boldsymbol{Y}$, $\boldsymbol{Z}$ and $\alpha>0$ obeying the optimality conditions of Lemma LABEL:lemma:KKT. This is the objective of the next subsection.

C.3 Construction of Dual Certificateslabelsec:DualConstruction

where $\boldsymbol{E}$ and $\boldsymbol{E}^{\perp}$ are defined to be

for some sufficiently large constant $c_{10}>0$.

Construction of $\boldsymbol{Y}$ and $\boldsymbol{Z}$: define $\boldsymbol{Y}$ and $\boldsymbol{Z}$ such that

With the above construction procedure, one can easily verify that:

Furthermore, from Lemma LABEL:lemma:MeanApprox one can obtain

This taken collectively with (LABEL:eq:DefnMm) and the assumption (LABEL:eq:Lambda_Range) ensures that

Consequently, we will establish that $\boldsymbol{Y}$ and $\boldsymbol{Z}$ are valid dual certificates if they satisfy

Such conditions will be established through the following lemmas.

labellemma:BoundYl_ZlThere are some universal constants $c_{0},c_{1}>0$ such that

with probability exceeding $1-\frac{1}{(mn)^{4}}$.

See Appendix LABEL:sec:Proof_lemma:BoundYl_Zl.∎

See Appendix LABEL:sec:Proof_lemma:BoundYtrue.∎

Combining Lemmas LABEL:lemma:BoundYl_Zl and LABEL:lemma:BoundYtrue yields that there exists an absolute constant $c_{0}>0$ such that if

So far we have justified that $\boldsymbol{Y}$ and $\boldsymbol{Z}$ satisfy (LABEL:eq:RemainingCondition), thereby certifying that the proposed algorithm correctly recovers the ground-truth matching.

Appendix D Proofs of Auxiliary Lemmaslabelsec:ProofAuxiliaryLemmas

Denote by $\overline{\boldsymbol{A}}:={\bf 1}_{N}\cdot{\bf 1}_{N}^{T}$. From Bernstein inequality, $n_{i}$ sharply concentrates around $np$ such that if $p>\frac{c_{6}\log^{2}\left(mn\right)}{n}$

with probability exceeding $1-(mn)^{-10}$, where $c_{5},c_{6}>0$ are some absolute constants.

The bound (LABEL:eq:ni_np_gap) also implies that

with probability exceeding $1-(mn)^{-10}$, which implies that

This allows us to bound the deviation of $\boldsymbol{A}$ from $\overline{\boldsymbol{A}}$ as follows

On the other hand, it follows immediately from (LABEL:eq:ni_np_gap) that

D.2 Proof of Lemma LABEL:lemma:MomentMethodlabelsec:Proof_lemma:MomentMethod

By following the same procedure and notation as adopted in [48, Page 119], we divide all non-vanishing $k$-cycles into $\left(k/2\right)^{k}$ classes based on the above labeling order; each class is associated with $j$ ($1\leq j\leq k/2$) edges $e_{1},\cdots,e_{j}$ with multiplicities $a_{1},\cdots,a_{j}$, where $(e_{1},\cdots,a_{1},\cdots,a_{j})$ determines the class of cycles and $a_{1}+\cdots+a_{j}=k$. Since there are at most $n^{j+1}$ distinct vertices, one can see that no more than $n^{j+1}$ cycles falling within this particular class. For notational simplicity, set $K=\sqrt{n}$, and hence $\|\boldsymbol{M}_{ij}\|\leq K$. By assumption (LABEL:eq:M_block_assumption), one has

Thus, the total contribution of this class does not exceed

By summing over all classes one obtains the crude bound

If we set $k=\log\left(mn\right)$, then from Markov’s inequality we have

Since $n^{\frac{1}{\log n}}=O\left(1\right)$, there exists a constant $c_{0}>0$ such that

D.3 Proof of Lemma LABEL:lemma:SpectralGapTightlabelsec:Proof_lemma:SpectralGapTight

When $\mathcal{G}\sim\mathcal{G}(n,p)$, the adjacency matrix $\boldsymbol{A}$ consists of independent Bernoulli components (except for diagonal entries), each with mean $p$ and variance $p(1-p)$. Lemma LABEL:lemma:MomentMethod immediately implies that if $p>\frac{2\log\left(mn\right)}{n}$, then

with probability at least $1-(mn)^{-5}$. That said, there exists an absolute constant $c_{1}>0$ such that

with probability exceeding $1-(mn)^{-5}$.

On the other hand, from Bernstein inequality, the degree of each vertex exceeds

with probability at least $1-\left(mn\right)^{-10}$, where $c_{2}$ is some constant. When $p>\frac{2\log\left(mn\right)}{n}$, $\mathcal{G}$ is connected, and hence the least eigenvalue of $\boldsymbol{L}$ is zero with the eigenvector ${\bf 1}_{n}$. This taken collectively with (LABEL:eq:AdjMatrixGnp) and (LABEL:eq:DegreeMatrixGnp) suggests that when $p>\frac{c_{3}^{2}\log^{2}\left(mn\right)}{n}$, one has

D.4 Proof of Lemma LABEL:lemma:KKTlabelsec:Proof_lemma:KKT

From Assumption (LABEL:eq:Y-tangent-space), one can derive

where the first inequality follows from (LABEL:eq:PSD_dd_H), and the last equality follows from Assumption (LABEL:eq:S_construction).

Putting (LABEL:eq:YdH_non-neg) and (LABEL:eq:ZH_non-neg) together gives

which follows since all entries of $\boldsymbol{d}$ are strictly positive. This contradicts with (LABEL:eq:PSD_dd_H). Consequently, we must either have $\boldsymbol{H}={\bf 0}$ or $\sum_{i\neq j}\left\langle\boldsymbol{Z}_{ij},\boldsymbol{H}_{ij}\right\rangle>0$. This together with (LABEL:eq:ZH_positive_Y) establishes the claim.

See Appendix LABEL:sec:Proof_lemma:PgtH_H.∎

D.5 Proof of Lemma LABEL:lemma:BoundYl_Zllabelsec:Proof_lemma:BoundYl_Zl

for some absolute constant $c_{16}>0$, where the last inequality follows from Lemma LABEL:lemma:Concentration.

Put in another way, there exists a universal constant $c_{6}>0$ such that

holds with probability exceeding $1-\frac{1}{(mn)^{10}}$. This follows from Lemma LABEL:lemma:Concentration.

with probability at least $1-\frac{1}{(mn)^{5}}$. This combined with (LABEL:eq:A_bound) yields

with probability at least $1-\frac{3}{(mn)^{5}}$, where $c_{11}$ is some universal constant.

with probability exceeding $1-\frac{1}{\left(mn\right)^{10}}$.

D.6 Proof of Lemma LABEL:lemma:BoundYtruelabelsec:Proof_lemma:BoundYtrue

for some absolute constant $c_{5}>0$, where the second inequality follows from the concentration result stated in Lemma LABEL:lemma:Concentration.

This taken collectively with (LABEL:eq:BoundYtrue) yields that

On the other hand, we know from the construction procedure and Lemma LABEL:lemma:MeanApprox that

D.7 Proof of Lemma LABEL:lemma:PgtH_Hlabelsec:Proof_lemma:PgtH_H

Recall that $n_{i}$ denotes the number of sets containing element $i$, and that

From our assumption that $\frac{n^{2}}{n_{i}n_{j}}\neq\frac{n}{n_{i}}+\frac{n}{n_{j}}$, we can derive

References