Optimal detection of the feature matching map in presence of noise and outliers
Authors: Tigran Galstyan
Arshak Minasyan
Arnak S. Dalalyan
Venue: NeurIPS 2021 Submitted (2021)

Abstract: We consider the problem of finding the matching map between two sets of $d$-dimensional vectors from noisy observations, where the second set contains outliers. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated. The main result shows that, in the high-dimensional setting, a detection region of unknown injection may be characterized by the sets of vectors for which the inlier-inlier distance is of order at least $d^{1/4}$ and the inlier-outlier distance is of order at least $d^{1/2}$. These rates are achieved using the estimated matching minimizing the sum of logarithms of distances between matched pairs of points. We also prove corresponding lower bounds establishing optimality. Finally, we report the results of numerical experiments on both synthetic and real world data that illustrate our theoretical results and provide further insight into the properties of the estimators studied in this work.

Optimal detection of the feature matching map in presence of noise and outliers
Anonymous Author(s)
Affiliation Address email
Abstract
We consider the problem of finding the matching map between two sets of d- dimensional vectors from noisy observations, where the second set contains outliers. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated. The main result shows that, in the high-dimensional setting, a detection region of unknown injection may be characterized by the sets of vectors for which the inlier-inlier distance is of order at least ///4 and the inlier-outlier distance is of order at least d!/2 These rates are achieved using the estimated matching minimizing the sum of logarithms of distances between matched pairs of points. We also prove lower bounds establishing optimality of these rates. Finally, report the results of numerical experiments both synthetic and real world data that illustrate our theoretical results and provide further insight into the properties of the estimators studied in this work.
Introduction
16 Finding the best match between two clouds of points a problem encountered in many real problems. In computer vision, one can look for correspondences between two sets of local descriptors extracted from two images. In text analysis, one can be interested in matching vector representations of the words of two similar texts, potentially in two different languages. The goal of the present work is to gain theoretical understanding the statistical limits of the matching problem.
In the sequel, we use the notation [n] = {1..... ......., n for any integer n. and define || as the Euclidean norm Rdd Assume that two independent sequences X = (X,; E [n]) and Y (Y;; i E [r]) of independent vectors are generated such that X, and Y, are drawn from the same distribution P. on Rd for every [n]]. The statistician observes the sequence X and shuffled version X & of the sequence Y. More precisely, X such that X (1) for some unobserved permutation n." The goal of matching is to estimate the permutation x from data (xx*). ). In the case of Gaussian distributions P:, this problem has been studied in (Collier and Dalalyan, 2013, 2016). Clearly, consistent estimation of the matching map x impossible if there are two data generating distributions P; and P, that are very close. In (Collier and Dalalyan, 2013, 2016), precise quantification of the separation between these distributions is given that enables consistent estimation of .². Furthermore, it is shown that the permutation estimator minimizing the sum of logarithms of pairwise distances between the elements of X and the elements of the shuffled version X is optimal estimator of .:
x²).
In this paper, we extend the model studied in (Collier and Dalalyan. 2016) to the case when the set X* contaminated by outliers. The number of outliers supposed be known and is equal to m n. where X and x are the sizes of considered two sequences, however the indices of the
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

An unexpected finding of this work that the "degree" of heteroscedasticity of the model has a strong impact the separation distances and the detection regions (sets of values of (Rinvin- Rin-ou) for which it is possible to detect the feature map π )²). This is in sharp contrast with the outlier-free case, where consistent estimation requires x to be at least of order log n////1 irrespective from the behaviour Without outliers
With outliers this paper
(Collier and Dalalyan, 2016)
known o² or all equal o's
LSNS is optimal
LSNS is optimal [Thm.. 1]
R ž (d log n)
Kin-in A Ku--out Z (dlog(nm))
unknown o² Ouax/ mmi SC
LSL is optimal
LSL is optimal [Thm. 4]
Kin-in 2. (d log(nm)) & Rin-out 2 d2/2
R ž 1)/4
unknown o² arbitrary
LSL. is optimal [Thm. 2,
Kináin A Kin-out Z d2/2
Table A brief overview of the contributions in the high-dimensional regime d 2 c clog n. The table provides the condition on the normalized inlier-inlier distance Kin-in and inlier-outlier distance Fin-out- making possible to consistently detect the matching map between two sets of d-dimensional vectors. LSL and LSNS refer to least sum of logarithms and least sum of normalized squares, respectively.
outliers are unknown. All the distributions are assumed in this paper to be spherical Gaussian, although all the probabilistic tools used in the proofs have their Gaussin counterparts. Thus, we consider that two spherical Gaussian distributions Pi NN(u,, La and P2 NNa(u2, IāIa) are well separated if the "distance noise ratio" <P,,, P2) || μell of o is large. Main findings of (Collier and Dalalyan, 2016), in terms of smallest separation distance k = minize K( P; Pj) are summarized in the second columns of Table 1. Likewise, the last column of the table provides a summary of the contributions of the present paper in terms of Rin-in = min k(P,, P3) and a Rin-out min,,j x x(P,, Q2). where ...... mm are the distributions of the outliers.
of variances of P.. We prove in this work that in the high dimensional regime d 2 clog which is arguably more appealing than the low dimensional regime d S clog n, the following statements are true:
If there is no heteroscedasticity, i.e., when all the variances are equal, consistent estimation of n" is possible if and only if R = Kin-in A Rin-out is at least of order (d (olom(m)))33 1/4 This is the same rate as in the outlier-free case.
If the heteroscedasticity is mild, i.e., all the variances are of the same order, the condition Kin-in 2 (d is the same as in the previous item, but the stronger condition
54
Kin-out 2 d2/2 is needed for the inlier-outlier separation distance.
Finally, in the general heteroscedastic setting both Kin-in and Kin-out should be at least of order d²'2, Furthermore, in all these cases consistent estimation performed by the same estimator: the Least Sum of Logarithms (LSL).
37
Note also that the empirical evaluation done in this paper shows that LSL is interesting not only from the theoretical but also from the practical point of view.
Agenda Section 2 describes the framework of the vector matching problem and introduces the ter- minology used throughout this paper. Precise statements of the main theoretical results are gathered in Section 3. The prior work is briefly discussed in Section 4. Section 5 contains numerical experiments carried out both for synthetic and real data. A brief summary and some concluding remarks are presented in Section 6. Proofs of all theoretical claims are deferred to the supplemental material.
Problem Formulation
We begin with formalizing the problem of matching two sequences of feature vectors (X....., X,)) and (Xt....,X) X with different sizes and m such that m 2 2 2. In what follows, we assume
We use the notation La for the d d identity matrix

---

σ (o...... ,n)) of = (o .oi.....ot o are positive real numbers corresponding to the magnitudes of the noise contaminating each feature, that the observed feature vectors are randomly generated from the model
X + oiE.
== 1...,,, and j 1, 1...., m.
X - 0f + +
In this model, illustrated in Figure 1, it is assumed that
0 (01,... 0n) and 0* (ot.... 0th are two sequences of vectors from R corre- sponding to the original features, which are unavailable,
En and ,,...., & are two independent sequences of i..d. random vectors drawn from the Gaussian distribution with zero mean and identity covariance matrix.
The simplest special case of (I), considered in (Collier and Dalalyan, 2016), corresponds to the situation where perfect matching exists between the two sequences 0 and 0² This means that and, for some bijective mapping n" [n]] + [ni], 0, 0 Pt(; for all E [nx.. In the general case, both X (X1..... X,)) and X = (X)..... X may contain outliers, i.e. feature vectors that have no corresponding pair. In such situation, it merely assumed that there exists set C [n] and injective mapping "' S + [m]] such that
8 = 00) and o, -; (0):
ViES.
(2)
In this case say that the vectors {X; i [n] (} and (xj ij [m] \ (S)) are outliers. The ultimate goal is estimate the feature matching map x².
In this work we consider the case when S = [n] and m > n. This means that only the larger set of feature vectors, namely X contains outliers. Let us also define the set O₂- - [m] \ Im(x*), which contains the indices of outliers and satisfies 10,- in X, as well as those vectors from X that are not outliers, are called inliers.
n. Naturally, the feature vectors contained
In this formulation, the data generating distribution is defined by the parameters 0¹ and π². We omit the set of parameters O and ar, since they automatically identified using x², 0 and o+ by the formula (0., ..)) = (0* (a): o *+)()) for i E [n]. Since our goal is to match the feature vectors, we focus our attention on the problem of estimating the parameter क only, considering 0* and a+ as nuisance parameters. In what follows, we denote by
the probability distribution of the sequence (XI,.... Xn, Xf...... ..... x defined by (1) under condition (2) with S [n]]
We are interested designing estimators that have an expected error smaller than prescribed level under the weakest possible conditions on the nuisance parameter O* and noise level a². Clearly, the problem of matching becomes more difficult with hardly distinguishable features. To quantify this phenomenon, we introduce the normalized separation distance Rim-in = Fi (0', a x²) and the normalized outlier separation distance Rin-our = Rin-out (0* o+ x²), which measure the minimal distance-to-ne toise ratio between inliers and the minimal distance-to-noise ratio between inliers and outliers, respectively. The precise definitions read as
110| 11
100 0511
Kin-in
min 100 jti
- (o.² + 2/211/2
Rin-out
min ig0 jEO.-
(a + 2/31/2
(3)
Notice that Rin-in can be rewritten as
Rinin = min |00 1
i.jEIn] (o? + 0f)1/2
Clearly, if Kin-in O or, Kin-out = O, there are two identical feature vectors X In such a situation, assuming oz'5 rs's are all equal, the parameter x" is nonidentifiable, in the sense that there exist two different permutations गं and тद such that the distributions po "tat and Por oa .ew coincide. Therefore, to ensure the existence of consistent estimators of x* it necessary to impose the conditions Kin-in and Rin-out > O. Moreover, good estimators are those consistently estimating T even if either Kin-in or Kin-our are small. We are interested here in finding the detection boundary in terms of the order of magnitude of (Rin-in; Rin-out). More precisely, for any given E (0, 1) we wish to find a region Ro in IR? such that:
3

---

X1
X2
X3
X1
X5
X6
X7
X
x
Figure 1: Illustration of the considered framework described in (1). We wish to match a set of 7 patches extracted from the first image to the patches from the second image. The picture on the left shows the locations of patches as well as the true matching map π² (the yellow lines).
There an estimator fn.m of xt satisfying P Por , (+ 7 x²) I a for every (0* 10",0","" ,,,,,)))))
lying in the detection region, i.e., for which (Fin-in Fin-out) E Rn,mdd
< 1 such that for any estimator An.m of π², we can find a parameter value (0" of, ) in the region {(0", ,²,x*) x²) π with a probability larger than a.
There is a constant
(Rin-in: Fin-out) E CR n.m.a) such that म fails to detect
Let us make two remarks. First, note that in the outlier-free case considered in (Collier and Dalalyan, 117 2016), Fin-out is meaningless and, therefore, the detection region one-dimnniional R Thus, it is necessarily half-line and is proven to be of the form Rin-in 2 C(log "/a) 1/2 v (dlog for some universal constant C. Second, the aforementioned definition of the detection region t n.m.d does not guarantee its uniqueness (even up to scaling by universal constant). This is in contrast with the outlier-free case. To overcome this difficulty, we look for Ra, of the form Mi--in: +o0)= x oat, +o0) with the smallest possible threshold ou for the normalized inlier-outlier distance Fin-out-
20
Main theoretical results
In this section, we have collected the main theoretical findings of the paper. When the noise is homoscedastic, i.e., when a's are equal, the results obtained by Collier and Dalalyan (2016) in 26
the outlier-free setting can be easily extended to the setting with outliers. Therefore, in the present paper, we focus on the heteroscedastic case. For the sake of clarity of exposition, we will present the results in the case of known variances a, of prior investigating the more interesting case of unknown variances.
The detection regions we study below are based on the profile maximum likelihood estimator. The model presented (1) has the parameter E = (0*, a² T), while the observations are the sequences of feature vectors X and X The negative likeliield of this model is given by
t, (x;
Σ i=1
|[:
OF m(8)
1 log(a
x(())
X
log( log(of))
20 7(1)
2
20122
The profile negative log- ligeliielihod is then defined as the minimum with respect to (0", at) of the log- likelikel (E: (X,x*))
3.1 Warming up: known variances o,
2
One can check that the minimization with respect to 0* leads to the variance-dependent cost function
3
X - X
(n of (x,
Σ
log o m(1)) + Σ
j=1 2 (3)).
(4)
0. (()
2
When m = n and there is no outlier, the last two sums of the last display do not depend on a and, therefore, the maximum profile likelihood estimator of nt is obtained by the Least Sum of

---

Normalized Squares (LSNS) criterion
"1 | X x()) 11
" m.
E arg min π
(5)
o o 7(8)
where the minimum is over all injective mappings |n| + [m]. This, and the other estimators defined in this work, can be efficiently computed using suitable versions of the Hungarian algorithm
(Kuhn, 1955, 2010: Munkres, 1957). As shows the next theorem, it turns out that even when m > the estimator A n, defined above leads to an optimal detection region.
Theorem (Upper bound for LSNS) Let a E (0, 1) and condition (2) be fulfilled. the separation distances Kin-in and Rin-out corresponding to (0², o², x²" and defined in (3) satisfy the condition
min Fei--in: Fun-out) 2 { (dlog(Anm/a)) 1/4 (2 (2log(8mm/a)) /2)
(6)
then the LSNS estimator defined in (5) detects the true matching map xO with probability at least 1 On, that
Pe of (ALSS =T) =²)
The similarity- its statement and its proof- of this result is to its counterpart in the outlier-free setting might suggest that the presence of outliers does not make the problem any harder from statistical point of view. However, this is not true in the more appealing setting of unknown variances.
3.2 Detection of for unknown and arbitrary variances o
The LSNS procedure analyzed in Theorem 1 exploits the values of known noise variances to normalize the squares of distances between vectors X; and X T(() Therefore, LSNS inapplicable in the case of unknown noise variances. Instead, we consider the Least Sum of Logarithms (LSL) estimator
LSL n2
arg mi(m [m)]
min
log ||
X 7(0)
where the minimum is over all injective maps [n]] + [m]. This estimator can be seen as the minimizer of criterion defined as the minimum of the cost function from (4) with respect o+ under the constraint min minjzlm(() o. 2 mmins for some fixed (but unknown) constant T >> 0.
To provide quick overview of what follows, let stick in the remaining of this paragraph to the case log(nm) = (dd) so that the right hand side of (6) is of order (d (og(m)))) 1/4, Recall that in the outlier-free free case, the LSL estimator has been shown to perform as well as the LSNS while having the advantage of not requiring the knowledge of variances of (Collier and Dalalyan, 2016). Somewhat uncxpectedly, the situation is significantly different in the presence outliers. Indeed, the best we manage to prove in the presence of outliers is that the detection of the matching map by LSL is possible whenever min Ri-inn Rin-out CVd for some sufficiently large constant C. The precise statement being given in the next theorem, let us mention right away that the discrepancy between this rate v and the rate (d (oo(m))) 1/4 in (6) is due to the inherent hardness of the setting and not merely artefact of the proof. This will be made clear below.
Theorem (Upper bound for LSL) Let E (0, 1/2) and condition (2) be fulfilled. If the separa- tion distances Kin-in and Kin-oot corresponding to (0", a² π²)) and defined by (3) satisfy
min finffe Fin-in Fin-out 2 V2d + of (nmm/a))) 1/4 (11////3llggggggg (3log(Snm/ )
(8)
then the LSL estimator (7) detects the matching map n² with probability least a, that
Po o nn = mT" 2 1 a
120 This result disappointing since requires the distance between different feature vectors to be larger *76 than 2dd in order to be able to consistently estimate the matching map л². As we show below, without any further condition (for instance, on the noise variances), this rate cannot be improved.
*24
5

---

Furthermore, the rate vd is optimal not only for LSL but also for the larger class of so called distance based M -estimatorss
We will say that an estimator Hn of nT" is a distance based M-estimator, if for a sequence of non- decreasing functions Pi R2 R. 1, -..... n,, the following is correct
R E arg
min
X 7(() I))
where the minimum is over all injective mappings и [n] [m]] We denote by M the set of all distance based M-estimators. We show that there is indeed setup where Kin-in Kin-out is large as 0.2vd but any estimator from M fails detect x² with probability at least 1 /4. The next theorem formalizes the described result.
Theorem (Lower bound) Assume that m n 2 4 and 422 log((n)) There exists a triplet (o+, 0*, π²)) such that Fin-in Rin-out /d/20 and
inf P REM
o . ( + T-) 1/4.
(9)
-2 The proof of this theorem, postponed the appendix, is constructive. This means that we exhibit triplet (a 00,00, x²) satisfying (9). Careful inspection shows that in the case d (log(mm) * the same triplet satisfies Em A Fin X Vlog (nm) and (9) still true. This implies that the order of magnitude of the right hand side of (8) is optimal both in the high-dimensional regime > 422 log( (4n) and the low-dimensional regime d < 422 1o2log(4 (og(4)). This shows the optimality of LSL among all estimators from M. Note that the estimator nn. does not belong to the family of distance based M-estimators. Furthermore, in the low dimensional regime d = O(log(nm)), the separation rate of the LSL, /log(mm), is the same that of the LSNS.
In the next section we show that under some mild conditions on a² it is indeed possible to obtain different rates for Ki and Rin out, namely we show that if Kin.in Z /d1/1 and Fin Z dz/2 then the LSL estimator detects correct matching with high probability.
3.3 Detection of x² for unknown and mildly varying variances of
The results of the last two theorems are disappointing, since they indicate that the features should be very different from one another for detection of the matching map to be possible. An interesting finding, presented below, is that strong constraint can be significantly alleviated in the context mild 222
heteroscedasticity. By mild heteroscedasticity we understand here the situation in which all variances
of are of the same order of magnitude.
x6 Theorem (Upper bound under mild heteroscedasticity) Let ra = max;,(ot/off < co. the separation distances Rin-in and Rin-out defined in (3) satisfy
Rinvin 2 2(4d (olllom((///))) 1/4 222 44mm/a)) 1/2
Kin-out 2 22(ro - 1)d + 24r (lgg(t//////////mmmmmm 1/4 + 2(2ra log( (og(4nm/a)) 1/2
>0 then the LSL estimator (7) detects the matching map nt with probability least a, that
P P (nmm TT" 2 a-a
230
Note that a lower bound similar to that of Theorem 3 can be proved in the case of mild heterescodestac- ity as well, showing that there is an example for which Kin-in is of order d²/4, Kin-out is of order d///2 and any estimator from M fails to detect n with probability at least 1/4.
350
210
212 We complete this section by summarizing the joint contribution of Theorems 1 to 4. To simplify this discussion, we consider two cases: high-dimensional case refers to d > log 00g(4m//a (presented in Table and low-dimensional case refers the condition d < log( (og(4m//a) J. In the high dimensional setting with arbitrary noise variances, the detection region for the LSL. estimator is given by [Rimin A Kin-out > 15vdy. which is much worse than the detection region for LSNS, {Rin-in A Rin-out 2 8(d log log (4nm/a)) obtained in the known- scenario. Somewhat surprisingly, in such
214

---

Greed
Greedy
C2-
Eiror Rute
44
Fin-to
Pmp-ont
The performance of the methods (Greedy, LSS, LSL,, LSNS) the setup described in Exp- 1. Plots show the error rate (percentage of repetitions in which the estimated matching map differs from the true one) as a function of separation distances. The left plot illustrates that LSS, LSL and LSNS require much lower value of Rin-in in order to find the correct mapping. The left plot shows that there is clear improvement of the error when the inlier-inlier separation distance increases, while the right plot shows that the eπror rate might not be made small by augmenting Rm-ouu only.
Figure 2:
setting, even strong assumption on the outliers, such as requiring them to be at least at a distance 0.2vd of the inliers, is not enough for relaxing the assumption on the inlier-inlier separation distance. Finally, on positive note, in the intermediate case of mildly varying variances, the detection region for the LSL. estimator is of the form in 2 7(d (ooog44n////) 1/4; Rin 2 10vd). This means that if the outliers are at a distance Q (Vvd) of the inliers, then the LSL recovers the true matching under the same condition Riniin as in the outlier-free setting.
22
4 Other related work
Measuring the quality of the various statistical procedures of decision making by their minimal separation rates became the standard in hypotheses testing, see the seminal papers (Burnashev, 1979;
225
Ingster, 1982) and the monographs (Ingster and Suslina, 2003; Juditsky and Nemirovski, 2020).
397
Currently this approach is widely adopted in machine learning literature (Xing et al., 2020; Wolfer and Kontorovich, 2020; Blanchard al., 2018; Ramdas al., 2016; Wei al., 2019; Collier, 2012).
Beyond the classical setting of two hypotheses, it can also be applied to multiple hypotheses testing framework, for instance, variable selection (Ndaoud and Tsybakov, 2020; Azaïs and de Castro, 2020; Comminges and Dalalyan, 2012) or the matching problem considered here.
231
On the other hand, feature matching well studied problem computer vision. In recent years, great deal of attention was devoted to the acceleration of greedy matching algorithms, based on approximate and fast methods of finding nearest neighbors (e.g. Jiang al. (2016); Wang al. (2018); Wang (2011); 1); Harwood and Drummond (2016); Malkov and Yashunin (2020)). Another direction that helps improve feature matching problem is using alternative local descriptors (Rublee et al. 2011; Chen et al., 2010; Calonder et al., 2010) for given keypoints. Naturally, the question of how to chose keypoints arises, which is addressed, for instance, in (Bai et al., 2020; Tian et al., 2020). For more complete overview of the field we refer to (Ma et al., 2021) and references therein.
230
235
330
Finally, permutation estimation and related problems have been recently investigated in different contexts such as statistical seriation (Flammarion et al., 2019), noisy sorting (Mao et al., 2018), regression with shuffled data (Pananjady et al., 2017; Slawski and Ben-David, 2019), isotonic regression and matrices (Mao et al., 2020; Pananjady and Samworth, 2020; Ma et al., 2020), crowd labeling (Shah et al., 2021), and recovery of general discrete structure (Gao and Zhang, 2019).
241
20
26
Numerical results
210
In this section, we report the results of some numerical experiments carried out on simulated and real data. We applied aforementioned methods LSNS and LSL and computed different measures of their performance. To get a more complete picture, we included in this study the Least Sum of Squeres (LSS) estimator and the greedy estimator. LSS is unnormalized version of LSNS, given by
Ni
SLS n, E arg min
X X x(0) 1l
(10)

---

It coincides with LSNS in the case of homoscedastaic noise. The greedy estimator is obtained x09 by sequentially matching each vector from X to the nearest vector from X'. Experiments were implemented using python or matlab. For solving linear sum assignment problems such as (7) or (10), the generalized and improved versions of the Hungarian algorithm were used (Kuhn, 1955, 2010; 25 Munkres, 1957; Duff' and Koster, 2001), implemented in SciPy library (Virtanen et al., 2020).
Experiment 1: Synthetic data with random features We first randomly generated x². 0* and 237 as follows. We randomly sampled from uniform distribution on [0, 2] independent variables Tuj. i [m]. j E [d]. Then, (8)), are independently sampled from the Gaussian distribution with 0 mean and variance Tay. Additionally, for every 0 E 0* such that i & J=- (0) is an outlier), we incremented 340 every coordinate of f by i. Entries of of were sampled from the uniform distribution over [0.5, 2]. Sequences X and X were generated according to Section 2 with x. (i) = for i E [n]. We applied to this data the following matching algorithms: Greedy, LSS, LSNS and LSL.
a20
291
We chose n 100, m = 130 and d 50, and generated N 50 datasets according the foregoing process. For each dataset, we computed the 0-1 error of the considered estimators and the values of Rin-in Rin-out). We plotted in the left (resp., the right) panel of Figure 2 the error averaged over all datasets with a given value of Ri (resp. Rm In this specific example, we see that the error decreases fast with iiniin while there is no monotonicity of the error rate as a function of Run
200
209
207
Experiment 2: Synthetic data with deterministic features The second experiment is conducted on data generated by features 0² and variances o$ inspired by the example constructed in the proof of Theorem 3. More precisely, for some real numbers and b representing, respectively, the scale of inlier-inlier distance Ri and inlier-outlier distance Fun.out, we set 0% = [ka, 0 0f for l E [x]] and 4 = [na + kb, 0.... .TT. We also used decreasing variances of = 1 1/k3/² for ls E [m]] and true identity mapping गt (k)= = k for k E [n]]. We chose n = 100, m = 120 and dimension d' varying in the set 20, 40). For each pair of values (a, b) in suitably chosen grid, we repeated Peep 400
209
100
321
OOT.
times the experiment that consisted in generating data according to (1) and computing estimators LSS and #1.3,, defined respectively by (10) and (7). We then computed, for each pair (a. b) and for n.m each estimator LSS and LSL., the percentage of successful detection among "rep repetitions.
The obtained detection regions are depicted in Figure 3 in the form of heatmaps. This visualisation allows us to grasp the forms of the detection regions for the specific choice of parameters considered in this example. The first observation is that L.L is clearly superior to LSS for all the considered values of the dimension. Second, we clearly see the deterioration of the detection region when the dimension d becomes larger. Third, the values of Kin-out used in the plots are at least one order of 222
magnitude larger than those of Kin-in- This is in line with the claim of Theorem 4. We also observe in these pictures that successful detection occurs when ou- is larger than some threshold even if Ram-in is small. This must be nice feature of LSL. and LSS in this specific example, which unfortunately does not generalize to other examples as shown by our theoretical results.
204
230
Experiment 3: Real data example This experiment is conducted on the IMC-PT 2020 dataset from Jin et al. (2020) that consists of images of 16 different scenes with corresponding 3D point- clouds of landmarks, which are used to obtain (pseudo) ground-truth local keypoint matchings. For a given scene, we sampled 1000 pairs of distinct images of the same landmark with different camera locations, angles, weather conditions etc. For each image pair we generated 2D keypoints from aae
230
original set of 3D points (note that the same 3D point appears in both of the images, so we have ground truth keypoint matching between 2 images). Subsequently, we computed SIFT descriptors (Lowe, 2004) for every keypoint in images using Python OpenCV interface (Itseez, 2015). Some pairs of images being more challenging than others, we split the dataset into two sets of image pairs in order to gain more understanding on the behaviour of the algorithms. The challenging pairs are those for which the OpenCV default matching algorithm has accuracy less than 0.5. Then, for every image pair, we fixed randomly chosen 100 keypoints in the first image (and corresponding keypoints in the second image) and added outliers to the second image from the remaining keypoints. The outlier rate is chosen to be between 0% to 70%. Finally, descriptor matching algorithms were applied OpenCV default matching algorithm, LSS and LSL). Note that and o² from (1) are unknown, hence LSNS is not applicable. One can consider using the estimates ē and o² instead of a and o' xa in (5), but this beyond the scope of this paper.. Further details on this experiment along with some
234
*9
334 additional results are deferred to the supplemental material (Appendix D).
8

---

Detection region of LSL
Kin-in
Delection region LSS
64
63
Bin-in
64
61
Kin Figure 3: Heatmaps of the error rate of the LSL (top row) and the LSS (bottom row) estimators in Experiment 2. We chose n 100, m 120 and d {10, 20, 40) from left to right. The parameter a representing the scale of Rm-in and corresponding to y-axis varies from 0.02 to 0.08, whereas representing the scale of Kin-out and corresponding z-axis varies from 0.3 to 10. Dark colour means that probability of successful detection is close to (error rate close to zero).
Pin-out
Rin- out
Not challenging pairs
Challenging pairs
1.0
0.5
OpenCV
OpenCV
Accuracy
0.5 096
10%
20%
30%
40%
30%
80%
70%
0.0 07%
10%
200%
.00%
40%
30%
00%
70%
Figure 4: The estimation accuracy measured in the Hamming loss of the estimated matching in Exp. for different values of the outlier rate, (m--))/n, nn,n, varying from 0% to 70%. The medians of estimation accuracy both for challenging pairs (right plot) and simple pairs (left plot) of images from Temple Nara scene was computed using OpenCV, LSS and LSL matchers. The green region represents the interquartile range (lower and upper bounds being 25% and 75% percentiles, respectively).
The median estimation accuracy measured in the Hamming loss-for the image pairs from Temple Nara Japan scene-is plotted in Figure 4. Similar results for other scenes are presented in the supplemental material. The error bars with borderlines corresponding to 75% and 25% percentiles are also displayed. The first observation is that LSS and LSL outperform the OpenCV matcher in terms of Hamming distance. Second, the task of feature matching becomes harder with the growth of outlier rate, with a deterioration that seems to be linear in the rate of outliers. Notice that in this experiment the outliers can be very similar to the inliers and the separation condition imposed on m
3>9
Fun-out of Theorems 2 and 4, is violated. This implies that the larger the outlier rate the harder it is to find the correct match, causing larger number of mistakes.
21
Conclusion
314
We have investigated the detection regions in the problem of estimation of the matching map between two sequences of noisy vectors. We have shown that the presence of outliers one of the two sequences has a strong negative impact on the detection region. Interestingly, this negative impact is mitigated in the regime of mild heteroscedasticity, i.e., when noise variances are of the same order 318
of magnitude. In the extremely favorable case of homoscedastic noise (all variances are equal), the presence of outliers does not make the problem any harder, provided that the outliers are at least as different from inliers two distinct inliers different region in these different cases can be found in Table 1. The results of the numerical experiments conducted both synthetic and real data confirm findings and, furthermore, show the good behaviour of the LSL. estimator in terms of its robustness to noise and to outliers, not only in the problem of detection but also in the problem of estimation. In the future, plan investigate the case when both sequences contain outliers and to obtain theoretical guarantees on the estimation error measured by the Hamming distance.
another. Precise forms of the detection

---

References
Azaïs, J. M. and de Castro, Y. (2020). Multiple testing and variable selection along least angle regression's path.
111 Bai. X., Luo, Z., Zhou, L.. Fu, H., Quan, L., and Tai, C.-L. (2020). D3feat: Joint learning of dense detection and description of 3d local features. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR).
308
Blanchard, G., Carpentier, A., and Gutzeit, M. (2018). Minimax Fuclidean separation rates for testing convex hypotheses in Rd. Electron. J. Stat., 12(2)3313-33355.
Burnashev, M. (1979). On the minimax detection of an inaccurately known signal in white Gaussian noise background. Theory Probab. Appl., 24:107-111
Calonder, M., Lepetit, V., Strecha, C., and Fua, P. (2010). Brief: Binary robust independent elementary features. In Daniilidis, K., Maragos, P., and Paragios, N., editors, Computer Vision - ECCV 2010, pages 778-792, Berlin, Heidelherg. Springer Berlin Heidelberg.
33
Chen, J., Tian, J., Lee, N., Zheng, J., Smith, R. T., and Laine, A. F. (2010). A partial intensity invariant feature descriptor for multimodal retinal image registration. IEEE Transactions on Biomedical Engineering, 57(7):1707-177
341
30
Collier, O. (2012). Minimax hypothesis testing for curve registration. In Lawrence, N. D. and Girolami, M. A., editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma. Canary Islands, Spain, April 21-23, 2012, volume 22 of JMLR Proceedings, pages 245.245. JMLR.org.
36
347
Collier, O. and Dalalyan, A. S. (2013). Permutation estimation and minimax rates of identifiability. Journal of Machine Learning Research, W & CP 31 (AI-STATS 2013):10-19.
Collier, O. and Dalalyan, A. S. (2016). Minimax rates permutation estimation for feature matching. The Journal of Machine Learning Research, 17(1):162-19)) 192.
220
Comminges, L. and Dalalyan, A. S. (2012). Tight conditions for consistency of variable selection in the context of high dimensionality. Ann. Stat., 4065):2667-2666.
Duff, I. S. and Koster, J. (2001). On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM Journal on Matrix Analysis and Applications, 22(4):973-99)
326
Flammarion, N., Mao, C., and Rigollet, P. (2019). Optimal rates of statistical scriation. Bernoulli, 25(1):623-653
Gao, C. and Zhang, A. Y. (2019). Iterative algorithm for discrete structure recovery. arXiv preprint 191ivv1911.0100
220
Harwood, B. and Drummond, T. (2016). Fanng: Fast approximate nearest neighbour graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5713-5722.
Ingster, Y. (1982). Minimax nonparametric detection of signals in white Gaussian noise. Probl. Inf. Transm., 18:130-140.
20
Ingster, Y. I. and Suslina, I. A. (2003). Nonparametric goodness-of-ff testing under Gaussian models, volume 169 of Lecture Notes in Statistics. Verlag,.-Verlag, New York.
Itseez (2015). Open source computer vision library. https: http://gggh.b.cco///te////eee//
300
Jiang, Z., Xie, L.,, Deng, X., Xu, W., and Wang, J. (2016). Fast nearest neighbor search in the hamming space. In Tian, Q., Sebe, N., Qi, G.-J,, Huet, B., Hong, R., and Liu, X., editors, MultiMedia Modeling, pages 325-336, Cham. Springer International Publishing.
Jin, Y., Míshkin D., Mishchuk, A., Matas, J., Fua, P., Yi, K. M., and Tralls, E. (2020). Image Matching across Wide Baselines: From Paper to Practice. International Journal of Computer Vision
371
10

---

Juditsky, A. and Nemirovski, A. (2020). Statistical inference via convex oprimization. Princeton, NJ: Princeton University Press.
274
Kuhn, H. W. (1955). The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1-2):83-97.
Kuhn, H. W. (2010). The Hungarian Method for the Assignment Problem, pages 29-47. Springer Berlin Heidelberg, Berlin, Heidelberg.
377
Laurent, B. and Massart, P. (2000). Adaptive estimation of quadratic functional by model selection. Ann. Statist., 28(5): 1302-1333.
200
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60(2):91-110.
Ma, J., Jiang, X., Fan, A., Jiang, J., and Yan, (2021). Image matching from handcrafted to deep features: A survey. International Journal of Computer Vision, 129.
355
Ma, R., Tony Cai, T., and Li, H. (2020), Optimal permutation recovery in permuted monotone matrix model. Journal of the American Statistical Association, pages 1-15.
Malkov, Y. A. and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-836
230
Mao, C., Pananjady, A., and Wainwright, M. J. (2020). Towards optimal estimation of bivariate isotonic matrices with unknown permutations. Annals of Statistics, 48(6):3183-32000
Mao, C., Weed, J., and Rigollet, P. (2018) 8). Minimax rates and efficient algorithms for noisy sorting. In Algorithmic Learning Theory, pages 921-847. PMLR.
200
Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):22-38.
Ndaoud, M. and Tsybakov, sensing. IEEE Trans. Inf. Theory, 66(4):2517-2532.
(2020). Optimal variable selection and adaptive noisy compressed
Pananjady, A. and Samworth, R. J. (2020). Isotonic regression with unknown permutations: Statistics, computation, and adaptation. arXiv preprint arXiv:2009.02609.
Pananjady, A., Wainwright, M. J., and Courtade, T. A. (2017). Linear regression with shuffled data:
411 Statistical and computational limits of permutation recovery. IEEE Trunsactions on Information Theory, 328))3328-3300.
Ramdas, A., Isenberg, D., Singh, A., and Wasserman, L. A. (2016). Minimax lower bounds for 434 linear independence testing. In JEEE International Symposiun on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 965-969, IEEE.
Rublee, E., Rabaud, V., Konolige, K., and Bradski, G. (2011). Orb: An efficient alternative to sift or surf. In 2011 International Conference Computer Vision pages
Shah, N. B., Balakrishnan, S., and Wainwright, M. J. (2021). A permutation- based model for 42 crowd labeling: Optimal estimation and robustness. IEEE Transactions on Information Theory, 6166) 41844 4184.
Slawski, M. and Ben-David, E. (2019). Linear regression with sparsely permuted data. Electronic Journal of Statistics, 13(1):1-36.
42
Tian, Y., Balntas, V., Ng, T., Barroso-Laguna, A., Demiris, Y., and Mikolajezyk, K. (2020). D2d: Keypoint extraction with describe to detect approach. Proceedings of the Asian Conference on Computer Vision (ACCV).
86

---

Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., 47 Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M.. Wilson, J., Millman, K. J.. Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E.,, Carey, C. J., Polat, I., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I,, Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H.,, Pedregosa, F., van Mulbregt, P., and SciPy 1.0 Contributors (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272.
41
Wang, K., Zhu, N., Cheng. Y., Li. R., Zhou, T., and Long, X. (2018). Fast feature matching based on 46 I -naarstt k -means searching. CAAI Transactions on Intelligence Technology, 3(4):198-25 -977
Wang, X. (2011). A fast exact k-nearest neighbors algorithm for high dimensional search using k-means clustering and triangle inequality. In The 2011 International Joint Conference on Neural Networks, pages 1293-1299.
Wei, Y., Wainwright, M. J., and Guntuboyina, A. (2019). The geometry of hypothesis testing over convex cones: Generalized likelihood ratio tests and minimax radii. The Annals of Statistics, 47(2):994 - 1024.
Wolfer, G. and Kontorovich, A. (2020). Minimax testing of identity to reference ergodic markov 42 chain. In Chiappa, S. and Calandra, R., editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], 4N volume 108 of Proceedings of Machine Learning Research, pages 191-201. PMLR.
66 Xing, X., Liu, M., Ma, P., and Zhong, W. (2020). Minimax nonparametric parallelism test. Journal of Machine Learning Research, 21(94):1-47.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 1.
400
(b) Did you describe the limitations of your work? [Yes] See Section and Section 2 for informal statements, precise assumptions/limitations are presented in Section 3.
411
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
48c
2. If you are including theoretical results...
445
(a) Did you state the full set of assumptions of all theoretical results? [Yes]] See Section 3.
447
(b) Did you include complete proofs of all theoretical results? [Yes] See supplemental material (Appendix B).
445
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen-
431
tal material.
420
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 5 and supplemental material (Appendix D).
455
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 5 and supplemental material (Appendix D).
476
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
400
(a) If your work uses existing assets, did you cite the creators? [Yes]
411
(b) Did you mention the license of the assets? [N/A]
42
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
48
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you't re using/curating? [N/A]
46
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
471
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
472
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qV_pFVcntkV", "reviewer": "Reviewer_KyJs", "summary": "This paper considers the problem of matching two sets of vectors where the second set consists of a noisy version of the first set (inliers) together with outliers. Under a statistical framework, the paper develops theoretical bounds on the inlier-inlier and inlier-outlier separation that enable correct matching for a class of estimators including the Least-Sum-of-Logarithms (LSL). The approach follows Collier and Dalalyan, 2016, who considered the same problem without outliers. The LSL estimator is also evaluated using synthetic data, as well as in a semi-synthetic computer vision experiment using the IMC-PT-2020 real dataset for the task of feature matching towards obtaining point correspondences from two views.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers an interesting problem with many applications. It is very clearly written and the theoretical results appear to be original and have significance. The experiments show that LSL is an interesting estimator and are on par with the theory in the paper. \n\nOn the other hand, the paper would have been stronger if the authors had given results about the more general and practically relevant case, where both sets contain outliers. How much more difficult is that case? \nMoreover, the authors could have motivated the problem more from a general machine learning point of view. That is, they could have discussed several different machine learning applications. Instead, the application aspect of the paper including the real data experiment comes from computer vision. While this is not necessarily a drawback, there is a huge literature in computer vision regarding feature matching and from that point of view, the experiment is more of a proof of concept than anything else (e.g., one would have to also consider algorithm complexity, running times, parameter tuning e.t.c. to actually conclude that LSL outperforms OpenCV in this experiment). In my opinion it would have been more interesting to investigate a less explored and upcoming application, such as record linkage (e.g., see the work of Slawski and Ben-David already cited in the submission).\n\nOverall, this is a very well written theoretical paper, with good results, but also with plenty of room for improvement. \n\n********** POST-REBUTTAL *****************\nI thank the authors for their response, and I am glad my comments were well-taken. \n\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues as far as I can see. ", "review_text": "", "extra_scores": {"ethical_concerns": "No issues as far as I can see. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "jJp8mCa6anm", "reviewer": "Reviewer_AuhE", "summary": "This paper studies the problem of finding matches between two observations, one of which has outliers. It provides theoretical analysis about the conditions when using the Least Sum of Logarithms estimator can lead to optical solution. It studies different situation with regards to different cases of observations, providing the upper bound and lower bound theoretically. Experiments are conducted on synthetic datasets and one real image matching dataset.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n+: The paper gives theoretical analysis to an important problem in computer vision.\n+: Numerical results validate the theoretical results.\n\nWeaknesses\n-: While the theoretical studies should be encouraged, the present one seems to be less influentially in practice. The assumptions make the obtained results can not be a good guide to practical image matching problem, especially the challenging ones.\n-: Some obtained results from the theoretical analysis are well known ones, thus making the paper have less practical merits. For example, L312 “This implies that the larger the outlier rate the harder it is to find the correct match” L316 “We have shown that the presence of outliers in one of the two sequences has a strong negative impact on the detection region.”\n-: From the given theoretical results, it seems that the image matching problem should be better solved by optimizing the Least Sum of Logarithms estimator, instead of the widely used Least Sum of Euclidean distances. However, it does not the advantages of using LSL in real data experiments. In real data experiments, it compared with an OpenCV matcher, which is the bruteforce NN matcher based on Euclidean distances. For a fair comparison, the compared matcher should also be the Hungarian algorithm, because the better matching results can be caused by such advanced matching algorithm instead of the simplest NN matcher.\n-: Eq.(2) is not true in practice, especially for feature matching. In feature matching, although the matched features have identical original features \\theta, the observed features are most likely to be with different variance, i.e., \\sigma_i is not equal to \\sigma^{#}_{\\pi(i)} as shown in the latter of Eq.(2). Therefore, the theoritical results obtained by the paper is meaningless, or less useful in practice.\n-: The studied case described in L161 log(nm) = O(d) does not usually hold for keypoint matching problems.\n\nOther comments:\n1. Why use the Hamming loss to evaluate the matching performance in image matching problem? What is the definition of this loss?\n2. In supplement material, it would be better also provide the image matching results by the OpenCV matcher.\n\n\n============= post rebuttal =======================\n\nI appreciate the authors' feedbacks for my concerns, however, I didn't find them helpful.\n\n(1) After reading the reply of 1 and other reviews, I still can not get the main contributions having practical influence.\nAbout the reply of 2, I have clearly stated in the previous concerns that the real image matching experiments, the competitive method is the OpenCV matcher which is based on NN, not the LSS with Hungarian algorithm. \"In real data experiments, it compared with an OpenCV matcher, which is the bruteforce NN matcher based on Euclidean distances. For a fair comparison, the compared matcher should also be the Hungarian algorithm, because the better matching results can be caused by such advanced matching algorithm instead of the simplest NN matcher.\" -- This is the original comment.\n\n(2) The reply confuses my inital comment. For this point, I clearly pointed out that it is the variance being different, and of course, I mean the noise in descriptor. Please let me give an example, for image of RGB and NIR images, the descriptors of a same 3D point in the RGB images have a different variance to those of the same 3D point in the NIR images. This could also be the case of matching RGB images with different imaging conditions, such as by different cameras, different illuminations, etc.\n\n(3) For the case log(nm) = O(d), as the authors' given example shows, 8log(10) < 20 is much less than 128, about one order of magnitude smaller. Meanwhile, in many cases, the number of keypoints is about 2k, for this case, this does not hold. In addition, even in the authors' real experiments, they used 100 vectors per pair (see also the reply to Reviewer YuHQ), which apparently violates such conditions. Is this experiment non-meaningful? or there is no way to support the theoretical results by real image matching experiments?\n\nTo sum up, the feedbacks did not address my comments, I downgrade the initial score to reject. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Fg-exvP36hr", "reviewer": "Reviewer_YuHQ", "summary": "This paper provides a thorough investigation of how accurate detection regions can be mapped to each other.  The detection regions are typically represented by noisy vectors with outliers, and those problems can be formulated as how to finding the matching map between two sets of d-dimensional vectors. The investigation shows that the LSL estimator is robust to noise and outliers for both problems of detection and estimation. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an investigation which follows Collier and Dalalyan's work to explore the stability of noise observations. The paper is easy to read and understand; however, the originality and significance is more incremental. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. It only provides theoretic analysis and experiments to study how robust of the existing approach to the noisy observation. There is no attempt to further improve the existing algorithms, such as exploring the accuracy of LSL estimator with different error measurement. \n2. The author should consider the experimental evaluation with larger public known datasets.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While this paper considers an interesting twist on the matching problem, and is well written, the reviewers seem to indicate it would be of somewhat limited practical interest due to the existence of a much more powerful method (using a much heavier model) in openCV. And on the flip side the theoretical contributions are somewhat straightforward as they are primarily the analysis of a known (non-outlier) algorithm, but when used with assumptions on the outliers.


Decision: Reject