acceptodds
Under review as a conference paper at ICLR 2027

REFORMULATING MAXIMUM CONSENSUS AS A SET- HITTING PROBLEM FOR ROBUST ESTIMATION AND OUTLIER REMOVAL UNDER HIGH NOISE

Abstract

Maximum consensus (MAXCON) is a standard criterion for outlier removal and robust model estimation. Computing the exact optimal consensus set is a hard optimization problem as the standard big-M mixed-integer linear-programming (MILP) formulation scales poorly with the number of data-points, model dimension, and, most importantly, the percentage of outliers. To address this, we provide an exact reformulation of MAXCON as a set-hitting problem, and develop point- and subset-based criteria that remove guaranteed outliers, thereby reducing the size of the reformulated problem. In most cases the reduced problem either admits a tight LP relaxation or its greedy solution is provably optimal, so the exact optimum is certified without solving any MILP – removing the dependence on a licensed solver. In the remaining cases, the original MILP is solved over the much smaller pruned data-set, preserving tractability. On synthetic and real-world datasets with a large number of data-points and –% outliers, the proposed approach recovers the exact consensus set while running on average – faster than the MILP baseline, which often fails to solve the problem exactly even after exhausting a 48-hour runtime budget.

Primary area:
optimization
Keywords:
maximum-consensus, robust estimation, guaranteed outlier removal, set-hitting, discrete optimization, MILP

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NTsKOpenReview ↗
Rating
3(+2)
Confidence
4
Informativeness
3(+1)
Presentation
3(+1)
Soundness
3(+2)
Read review
Paper summary

The paper reformulates linear maximum consensus using hitting constraints on an infeasible subset of size d+1, invokes Helly's theorem for exactness, and develops point/subset consensus counts for pruning. The final algorithm combines pruning, greedy hitting sets, LP lower bounds, and a fallback MILP. Synthetic and affine-vision experiments report substantial speedups over the selected big-M Gurobi baseline, with many instances solved without a MILP. The central promised contribution is exact certification, not merely a faster heuristic.

Critical strengths

A practically important certification goal with potentially useful pruning statistics.

Critical weaknesses

a) For Theo. 2.2, take d=2, N=3, a_1=a_2=a_3=(1,0), b=(0,3,6), and epsilon=1. Any two residual slabs are disjoint, so the actual maximum consensus contains one point and requires two deletions. MC3 contains only the infeasible triple cut z_1+z_2+z_3>=1 and therefore permits a one-deletion solution. The claim that every subset of size at most d is feasible is false without an appropriate rank/general-position assumption. A correct Helly-based formulation must handle smaller infeasible witnesses or explicitly restrict the instance class (Sections 2 and Theorem 2.2).

b) Theo. 3.2 and Appx. A.1.2 confuse the fact that every optimal solution excludes some member of this subset with the subset containing a point excluded by every optimal solution. Consider y=ax+c, epsilon=0.1, and the six points (0,0),(1,0),(2,0),(3,10),(4,10),(5,10). The two horizontal triples are the only size-three feasible subsets and are both optimal; every point belongs to some optimum, so there are no global outliers as defined in Section 3. For S={(0,0),(3,10)}, rho=2 and n_lb=3, the feasible-triple count is zero, below binom(1,1)=1, contradicting the theorem's conclusion. The weaker joint-exclusion statement may still support optimum-preserving tuple pruning, but that is not the stated universal-outlier guarantee.

c) Alg. 2 has a non-terminating loop as presented in the paper. D is unchanged inside the repeat loop, SoS_o is reset and rebuilt from all rho-subsets of D, and termination requires SoS_o to become empty. A flagged subset remains below the same positive threshold after its containing tuples are removed, so it is flagged again indefinitely. On the six-point example above, all nine cross-line pairs have count zero, the two feasible triples remain unchanged, and every iteration returns the same nonempty flagged set. This is an executable-specification problem; it does not establish that the authors' undisclosed implementation has the same behavior, but the difference must be explained and the corrected procedure justified

Questions for authors

a) Which explicit assumption excludes the three-slab counterexample, or how is MC3 modified to include infeasible witnesses smaller than d+1? Please provide the corrected theorem and state its scope.

b) Is Theorem 3.2 intended to establish joint exclusion rather than the existence of an individually global outlier? Which downstream pruning/certification arguments remain valid under that weaker statement?

c) What stopping condition or processed-subset mechanism is used in the implementation of Alg. 2? Please show the corrected pseudocode and its output on the six-point example, including how termination and presentation of an optimal consensus are guaranteed.

14 comments

We are extremely thankful to the reviewer for the careful reading and the three counterexamples. We checked each of them, and each points to a real error in the submitted text. All three are fixed in the revision (changes in red). The fixes are to statements and to the pseudocode only; none of them changes the experimental results.


(a) Theorem 2.2 and the three-slab example

The reviewer is right. With a1=a2=a3=(1,0)a_1=a_2=a_3=(1,0), b=(0,3,6)b=(0,3,6) and ϵ=1\epsilon=1, every pair of slabs is disjoint, so nil∗=1n_{il}^*=1, yet MC3\mathcal{MC}3 admits a solution that deletes only one point. The claim in Section 2 that every subset of size at most dd is feasible is false, and we have removed it.

Corrected theorem and scope (answer to Question a). The exact condition is now part of the theorem:

Theorem 2.2 (revised). If UFd+1≠ϕ\mathcal{U}^{d+1}_{\mathcal{F}}\neq\phi, MAXCON is equivalent to the set-hitting problem MC3\mathcal{MC}3.

UFd+1≠ϕ\mathcal{U}^{d+1}_{\mathcal{F}}\neq\phi holds exactly when nil∗≥d+1n_{il}^*\ge d+1. Since this is the only condition, and Helly's theorem holds for arbitrary convex sets, no rank or general-position assumption is needed. This covers every instance with at least d+1d+1 points in consensus, including all instances in our experiments. In the reviewer's example UFd+1=ϕ\mathcal{U}^{d+1}_{\mathcal{F}}=\phi, since neither the triple nor any of the three pairs is feasible. That is precisely the excluded case.

Excluded case. UFd+1\mathcal{U}^{d+1}_{\mathcal{F}} is the first quantity Algorithm 3 computes. If it is empty, then nil∗≤dn_{il}^*\le d, and the optimum can be found easily by testing subsets of size d,d−1,…d, d-1, \dots for consensus. We have added a remark in Section 2 (in red), after the proof of Theorem 2.2, to cover this in the revised manuscript.

The proof remains unchanged for solutions with at least d+1d+1 inliers. What is new is the treatment of solutions with at most dd inliers in MC3\mathcal{MC}3, the reviewer's concern. Such solutions can be feasible in MC3\mathcal{MC}3 without being consensus sets, but none is optimal. We provide a 5-point example in Appendix A.1.1. Since their objective is at least N−d>N−nil∗N-d > N-n_{il}^*, while the complement of any optimal consensus set is feasible in MC3\mathcal{MC}3 with objective N−nil∗N-n_{il}^*, none of them can be optimal. If desired, they can be excluded with the valid constraint ∑izi≤N−(d+1)\sum_i z_i \le N-(d+1).


(b) Theorem 3.2: joint exclusion, not an individual global outlier

We have corrected Theorem 3.2 and it is a joint-exclusion statement. Its conclusion is that DSρ\mathcal{D}_{\mathcal{S}^\rho} is a global outlier-subset, which Section 3 defines as a subset whose points together cannot be part of any optimal solution. The proof in Appendix A.2.2 has been updated as well: if all ρ\rho points were inliers of an optimal consensus set of size nil∗≥nillbn_{il}^*\ge n_{il}^{lb}, their count would be at least (nillb−ρd+1−ρ)\binom{n_{il}^{lb}-\rho}{d+1-\rho}. Importantly, this condition is only used in Algorithm 2 to prune UFd+1\mathcal{U}^{d+1}_{\mathcal{F}} repeatedly, which then prunes D\mathcal{D} using the reduced UFd+1\mathcal{U}^{d+1}_{\mathcal{F}}.

In the six-point example, S=(0,0),(3,10)S=\\{(0,0),(3,10)\\} has count 0<(11)0<\binom{1}{1}. The theorem therefore concludes only that no optimum contains both points, which is true. It does not claim that either point is a global outlier, and none of the six is. We accept that the submitted text did not make this distinction explicit. The revision now states, right after Theorem 3.2, that a global outlier-subset need not contain a global outlier.

What remains valid (answer to Question b). With great pleasure, we inform the reviewer that we have added a new theorem, Theorem 3.3 (Global outlier pruning, proof in Appendix A.2.3), which shows that the updated Algorithm 2 still removes only global outliers. It uses joint exclusion only. Its proof rests on the following invariant:

(P) every (d+1)(d+1)-subset of every optimal consensus set remains in UFd+1\mathcal{U}^{d+1}_{\mathcal{F}}.

  • Tuple pruning preserves (P). Algorithm 2 removes only (d+1)(d+1)-subsets that contain a flagged ρ\rho-subset. By joint exclusion, no such (d+1)(d+1)-subset lies inside an optimum.
  • Point pruning removes only individual global outliers. A point is removed from D\mathcal{D} only when it lies in no remaining tuple of UFd+1\mathcal{U}^{d+1}_{\mathcal{F}}. If it belonged to an optimum, which has size at least d+1d+1, then by (P) it would lie in such a tuple. So the individual guarantee comes from this point-removal step, not from Theorem 3.2 itself.

Since Theorem 3.1, Corollary 3.4, the certificates of Proposition 4.1, and the exactness of MC3\mathcal{MC}3 on the pruned instance depend only on (P), all of them remain valid.

(c) Termination of Algorithm 2

The reviewer is right about the submitted pseudocode. It rebuilt the candidate set from all ρ\rho-subsets of D\mathcal{D}. A subset with count 00, such as the nine cross-line pairs in the six-point example, was then flagged again on every pass, so the loop never ended. The error was in the pseudocode only. We gave the six-point example to our code without making any changes, and it provided a correct consensus set. Our implementation has always counted just the ρ\rho-subsets that occur in a current tuple of UFd+1\mathcal{U}^{d+1}_{\mathcal{F}}.

Corrected pseudocode (answer to Question c). Line 3 of the revised Algorithm 2 restricts the candidates on each pass to subsets of current tuples: \mathscr{S}^{\rho}\leftarrow\big\\{\mathcal{D}_{\mathcal{S}^\rho}\subset\mathcal{D}_{\mathcal{S}^{d+1}_j}\\;\big|\\;\mathcal{D}_{\mathcal{S}^{d+1}_j}\in\mathcal{U}^{d+1}_{\mathcal{F}}\big\\}

  • Termination. Every flagged candidate lies in at least one current tuple, so each pass with Soρ≠ϕ\mathscr{S}^\rho_o\neq\phi removes at least one tuple. The loop therefore ends after at most ∣UFd+1∣+1|\mathcal{U}^{d+1}_{\mathcal{F}}|+1 passes. Once all tuples containing a subset have been removed, that subset is no longer a candidate and cannot be flagged again.
  • Implementation. The code counts ρ\rho-subsets over the current tuples and flags those with 0<count<(nillb−ρd+1−ρ)0<\text{count}<\binom{n_{il}^{lb}-\rho}{d+1-\rho}. This is the same set as the revised Soρ\mathscr{S}^\rho_o. It also stops if a pass removes no tuple. We will release the code.

Output on the six-point example (d=2d=2, ϵ=0.1\epsilon=0.1, ρ=2\rho=2, nillb=3n_{il}^{lb}=3). We ran the implementation on this example, and it matches the step-by-step trace now in Appendix A.1.2:

  • Algorithm 2.
    • UFd+1=1,2,3,4,5,6\mathcal{U}^{d+1}_{\mathcal{F}}=\\{\\{1,2,3\\},\\{4,5,6\\}\\}.
    • The candidates are the six within-line pairs. Each has count 1≮(11)1\not<\binom{1}{1}, so Soρ=ϕ\mathscr{S}^\rho_o=\phi and the loop ends after one pass. The cross-line pairs are never candidates.
    • UFd+1\mathcal{U}^{d+1}_{\mathcal{F}} is unchanged and Do=ϕ\mathcal{D}_o=\phi. Nothing is pruned, which is correct because every point belongs to an optimum.
  • Algorithm 3 then returns an optimal consensus set.
    • Corollary 3.4 gives nollb=3n_{ol}^{lb}=3.
    • The greedy hitting set over the 18 infeasible triples is Hg=1,2,3\mathcal{H}_g=\\{1,2,3\\}, with ∣Hg∣=3=nollb|\mathcal{H}_g|=3=n_{ol}^{lb}.
    • Certificate (i) of Proposition 4.1 therefore proves Hg\mathcal{H}_g optimal. The algorithm returns 4,5,6\\{4,5,6\\} (the line b=10b=10) without solving an LP relaxation or a MILP. The other optimum, 1,2,3\\{1,2,3\\}, is returned under a different tie-break.

In general, Stages I and II of Algorithm 3 stop only when they have an optimality certificate. Otherwise Stage III solves MC1\mathcal{MC}1 exactly on the pruned D\mathcal{D}, which by Theorem 3.3 still contains every optimum.


Summary of changes in the revision

  • Section 2: removed the false claim about subsets of size at most dd.
  • Theorem 2.2:
    • now requires UFd+1≠ϕ\mathcal{U}^{d+1}_{\mathcal{F}}\neq\phi, equivalently nil∗≥d+1n_{il}^*\ge d+1;
    • the proof handles solutions with at most dd inliers;
    • a remark covers the excluded case.
  • Appendix A.1.1: a 5-point example of such a solution.
  • Section 3: the joint-exclusion meaning of Theorem 3.2 is stated explicitly.
  • New Theorem 3.3, with proof in Appendix A.2.3: pruning is sound under any sequence of Algorithms 1 and 2.
  • Algorithm 2: candidates are restricted to subsets of current tuples, which guarantees termination.
  • Appendix A.1.2: a full trace of Algorithms 1–3 on the reviewer's six-point example.

Thank you for the detailed corrections. The revised Theorem 2.2 is sound under the nonempty feasible-tuple condition, and the joint-exclusion statement, invariant-based pruning argument, and revised candidate construction significantly addresses my original concerns. The six-point example is also handled correctly. One consistency issue remains: Algorithm 3 should explicitly invoke the small-subset fallback when �0��0�, before applying any pruning. As currently written, Algorithm 2’s final point-removal step would delete every point in the three-slab example. Theorem 3.3 should state the corresponding scope restriction, and its proof should correct the claim that nothing is pruned when �1��1�, which overlooks this final removal step. This appears to be a localized and readily correctable issue. Addressing it would make the revised theorem statements, proofs, and algorithm specification consistent and resolve my remaining concerns.

Reviewer_ZZgyOpenReview ↗
Rating
2
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the computational difficulty of solving the Maximum Consensus (MAXCON) problem exactly, particularly when the data contain a high proportion of outliers. The authors reformulate MAXCON as a minimum hitting-set problem using Helly's theorem. Based on this formulation, they derive point-level and subset-level consensus counting criteria to identify and remove guaranteed outliers. They further develop a multi-stage algorithm combining iterative pruning, greedy hitting-set construction, LP relaxation, and MILP fallback to obtain solutions with global optimality guarantees.

The method is evaluated on synthetic linear regression problems and two real-world computer vision tasks, affine image matching and affine epipolar geometry estimation. The results show substantial runtime improvements over directly solving the original MILP formulation, especially under high outlier ratios.

Critical strengths

1.Meaningful improvements in exact robust estimation. The paper addresses a challenging problem in robust estimation, where obtaining globally optimal solutions becomes computationally expensive as the outlier ratio increases. The reported improvements over the direct MILP baseline are substantial.

2.Theoretically motivated outlier pruning. The point- and subset-consensus counting criteria provide a useful way to reduce the optimization problem while preserving optimal solutions. Combining these criteria with greedy optimization and LP-based optimality certificates is a reasonable approach to avoiding expensive MILP computations.

Critical weaknesses
  1. The authors need to clarify how the reformulation differs from existing results. The paper presents the exact reformulation of MAXCON as a hitting-set problem as a central contribution. However, closely related formulations have been studied in the Maximum Feasible Subsystem (MaxFS) literature. For example, Amaldi et al. (2003) established the connection between infeasible subsystems and constraint removal, while Pfetsch (2008) explicitly formulated the complementary MaxFS problem as a set-covering problem over irreducible infeasible subsystems. These works are not discussed in the paper.

2.Some theoretical details and experimental evidence need further justification. In Theorem 3.2, the proof establishes that a subset cannot be entirely contained in an optimal consensus set, but this does not necessarily imply that the subset contains a fixed point that is an outlier in every optimal solution. This distinction matters for the claimed guarantees. In addition, the experimental evaluation lacks ablations of the main algorithmic components, making it difficult to determine how much of the observed speedup comes specifically from the proposed pruning criteria. The evaluation is also restricted to relatively low-dimensional problems, leaving the scalability with respect to model dimension insufficiently explored.

Questions for authors

Please refer to the weaknesses.

3 comments

We are extremely thankful to the reviewer for the constructive comments. We address each point below.


1. Relation to the MaxFS / IIS-cover literature

We thank the reviewer for pointing us to this literature. We agree that MAXCON can be viewed as an instance of the maximum feasible subsystem (MaxFS) problem. The complement of MaxFS can be formulated as covering all irreducible infeasible subsystems (IISs) (Amaldi et al., 2003), and Pfetsch (2008) solves this covering problem by branch-and-cut with heuristic IIS separation, limited to small instances as the worst-case complexity of branch-and-cut is exponential. We have added a paragraph discussing these works in the Introduction (in red).

Our formulation differs from the IIS-cover formulation in three respects:

  1. Fixed-size subsets instead of minimal IISs. MC3\mathcal{MC}3 hits all infeasible subsets of a fixed size d+1d+1, rather than the minimal IISs, which vary in size. Each subset is checked by an independent small LP. This avoids IIS separation, which is NP-hard (Amaldi et al., 2003), and the checks are trivially parallelisable.
  2. Counting-based pruning of global outliers. The fixed size is what makes our counting arguments possible. The point- and subset-consensus-count criteria (Theorems 3.1 and 3.2), the soundness of iterated pruning (Theorem 3.3), the upper bound on the number of inliers (Corollary 3.4) and the optimality certificates (Proposition 4.1) all count consensus subsets of size d+1d+1 against binomial thresholds. None of them has a counterpart in the IIS-cover formulation.
  3. Pruning before any integer program. These results prune the problem up front and often certify the optimum without solving an integer program at all: on all 260 synthetic and 58 of the 103 real instances (Figure 3).

To the best of our knowledge, exactness of the fixed-size formulation, which we prove via Helly's theorem (Theorem 2.2), has not been established before.


2a. Theorem 3.2: joint exclusion versus an individual global outlier

We agree with the reviewer regarding Theorem 3.2, and this has been fixed in the revised version. Theorem 3.2 establishes only joint exclusion: a flagged subset cannot be entirely contained in any optimal consensus set. It does not imply that the subset contains a point that is an outlier in every optimum. This is what Section 3 calls a global outlier-subset, and the revision now states explicitly, right after Theorem 3.2, that a global outlier-subset need not contain a global outlier.

With great pleasure, we inform the reviewer that we have added a new theorem, Theorem 3.3 (Global outlier pruning, proof in Appendix A.2.3), which shows that the updated Algorithm 2 still removes only global outliers.

All experimental results remain valid.


2b. Ablations of the main algorithmic components

We have added a per-stage breakdown to the revised manuscript (Figure 3, and Tables T1–T10 in Appendix A.4), reporting for every setup the stage of Algorithm 3 that solved it and the optimality certificate that terminated it. In summary:

  • by the end of Stage I (pruning and bound tightening), 249 of 260 synthetic and 46 of 103 real setups (6 affine, 40 epipolar) are certified optimal;
  • by the end of Stage II (LP relaxation of MC3\mathcal{MC}3), all 260 synthetic and 58 of 103 real setups (10 affine, 48 epipolar) are certified optimal, without solving any MILP (Figure 3);
  • on the 45 real setups that need a MILP, solving it over the pruned D\mathcal{D} succeeds on 43, whereas the same MILP over the full D\mathcal{D} succeeds on only 13 (30 out of memory, 2 timeouts). On these 13 setups, the average MILP time drops from 29,928 s over the full D\mathcal{D} to 1.5 s over the pruned D\mathcal{D}.

2c. Scalability with respect to model dimension

Limited scalability with respect to dd is not a shortcoming specific to our method: established theoretical hardness results limit how well any globally optimal method can scale with dd. Chin et al. (2018), cited in the paper, prove that MAXCON is W[1]-hard in the dimension dd: unless FPT = W[1], no exact algorithm runs in time f(d),poly(N)f(d)\\,\mathrm{poly}(\text{N}), so the exponent of N\text{N} in the runtime of any globally optimal method must grow with dd. Moreover, under a conjecture of Erickson et al. (2006), MAXCON cannot be solved faster than O(Nd)\mathcal{O}(\text{N}^d).

Within these limits, our real-world experiments cover model dimensions that are commonly encountered in computer vision problems: affine image matching and affine epipolar geometry. Note that affine image matching has 6 degrees of freedom; importantly, our set-hitting formulation reduces its effective dimension to d=3d=3 (Appendix A.2.6). To the best of our knowledge, ours is the first exact method to achieve such scalability, i.e. N≥100\text{N}\ge 100 with 50–80% outliers, at these model dimensions.

Thank you for the response from the author, but I have decided to keep the original score.

We thank the reviewer for reading our response. Since the reviewer's main empirical concern was how much of the observed speed-up comes specifically from the proposed pruning criteria, we would like to briefly highlight the additional evidence now included in the revised manuscript.

Contribution of each pruning criterion. We have added a new Appendix A.7 that reports the contribution of each pruning criterion: Table T14 summarizes it (reproduced below), Tables T15–T17 break down the synthetic results by dd, N\text{N} and poutp_{\text{out}} (per seed and on average), and Tables T1–T10 now give, for every setup, the number of points removed by Algorithm 1 and by Algorithm 2. These numbers are extracted from the logs of the reported runs. Theorems 3.1 and 3.2 are the two pruning criteria, applied by Algorithms 1 and 2 respectively, while Theorem 3.3 guarantees that the points removed by Algorithm 2 are also global outliers.

setupsPrunedby Alg. 1by Alg. 2
synthetic d=2d=210099.6%69.0%31.0%
synthetic d=3d=38098.9%41.6%58.4%
synthetic d=4d=48099.1%12.4%87.6%
real, affine4080.1%†16.8%83.2%
real, epipolar6391.6%7.1%92.9%

Pruned is the share of all optimal outliers that are removed during Stage I; the last two columns give the percentage share of the pruned points removed by Algorithm 1 and by Algorithm 2. †Computed over the 38 affine setups solved to optimality; for the other two the optimum is unknown.

The point criterion (Theorem 3.1) contributes most for d=2d=2. The subset criterion (Theorem 3.2) becomes dominant as dd grows, and on real data it accounts for 83–93% of all pruned outliers.

Effect of pruning on the overall runtime. As a result of this pruning, all 260 synthetic and 58 of 103 real setups are certified optimal without solving any MILP (Figure 3). On the 45 real setups that need a MILP, solving it over the pruned D\mathcal{D} succeeds on 43, whereas the same MILP over the full D\mathcal{D} succeeds on only 13 (30 out of memory, 2 timeouts). On these 13 setups, the average MILP time drops from 29,928 s over the full D\mathcal{D} to 1.5 s over the pruned D\mathcal{D}.

We would be more than happy to provide any additional information that the reviewer finds helpful.

Reviewer_aj4EOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper recasts maximum consensus as an exact set-hitting problem via Helly’s theorem, removing big-M hypothesis variables from the MILP. It provides point and subset consensus-count tests to certify global outliers, an inlier upper bound, and a three-stage algorithm consisting of prune-and-tighten, LP and greedy certificates, and MILP only on a reduced set. On synthetic linear regression and real affine and epipolar tasks with 50–80% outliers, it reports exact consensus recovery and large speedups over Gurobi MC1, often without solving any MILP.

Critical strengths
  1. The Helly-based reduction from consensus feasibility to set-hitting is clean and replaces big-M MILP variables with purely combinatorial hitting constraints.
  2. The point/subset consensus-count tests and inlier/outlier bounds are not just heuristics. Under a valid lower bound they identify guaranteed global outliers and can sharply reduce the instance.
Critical weaknesses
  1. Scalability is still conditional: the method requires enumerating/checking all (d+1)-subsets, i.e. C (N, d+1) = Θ(Nᵈ⁺¹) feasibility tests. This is polynomial in N only for fixed d and remains exponential in d. The paper does not establish practical scaling for d ≥ 5, very large N, tight ε, or weak nᵢₗˡᵇ.
  2. Validation breadth is insufficient: synthetic results use only 5 seeds with no variance/significance. Real-data “solver-free” claims are partial, with many affine cases still needing MILP. There are no ablations isolating pruning, bounds, LP/greedy certificates, or ε sensitivity, and the only exact baseline is Gurobi MC1.
Questions for authors

1.How are consensus counts Cℱᵈ⁺¹(·) and 𝒰ℐᵈ⁺¹ computed/stored in practice, and what are time/memory scaling results versus d and N beyond d = 4? 2. How sensitive are pruning power and optimality certificates to ε, inlier noise level, and the initial RANSAC lower bound nᵢₗˡᵇ? 3. Can you provide ablations for each stage: point pruning, subset pruning, RANSAC bound updates, greedy hitting set, LP relaxation, and final MILP fallback? 4. For real affine matching, why do 30/40 setups still require MILP, and how often is the LP relaxation integral versus the greedy certificate closing the gap? 5. The sizes of Tables 1 and 2 need adjusting.

1 comment

We are extremely thankful to the reviewer for the detailed comments and questions. We address each point below.


Scalability

Limited scalability with respect to dd is not a shortcoming specific to our method: established theoretical hardness results limit how well any globally optimal method can scale with dd. Chin et al. (2018), cited in the paper, prove that MAXCON is W[1]-hard in the dimension dd: unless FPT = W[1], no exact algorithm runs in time f(d),poly(N)f(d)\\,\mathrm{poly}(\text{N}), so the exponent of N\text{N} in the runtime of any globally optimal method must grow with dd. Moreover, under a conjecture of Erickson et al. (2006), MAXCON cannot be solved faster than O(Nd)\mathcal{O}(\text{N}^d). The Θ(Nd+1)\Theta(\text{N}^{d+1}) feasibility tests of our method are therefore within a factor N\text{N} of this bound.

Within these limits, our real-world experiments cover model dimensions that are commonly encountered in computer vision problems: affine image matching and affine epipolar geometry. Note that affine image matching has 6 degrees of freedom; importantly, our set-hitting formulation reduces its effective dimension to d=3d=3 (Appendix A.2.6). To the best of our knowledge, ours is the first exact method to achieve such scalability, i.e. N≥100\text{N}\ge 100 with 50–80% outliers, at these model dimensions.


  • Seeds, variance and significance. We have added per-seed runtimes for all synthetic runs (Appendix A.5) and a seed-variance analysis (Appendix A.6). Algo. 3 is faster on all five seeds in 43 of the 52 configurations, and faster in 230 of all 260 runs. A pooled one-sided Wilcoxon signed-rank test gives p=8.2×10−38p = 8.2\times10^{-38}.

Q1. Computation and storage of CFd+1(⋅)\mathcal{C}^{d+1}_{\mathcal{F}}(\cdot) and UId+1\mathcal{U}^{d+1}_{\mathcal{I}}; time and memory scaling

UFd+1\mathcal{U}^{d+1}_{\mathcal{F}} is computed once, with one small LP per (d+1)(d+1)-subset in parallel, and stored as an integer array of index tuples; all consensus counts are then obtained in a single vectorised pass over this array. UId+1\mathcal{U}^{d+1}_{\mathcal{I}} is built only on the pruned D\mathcal{D}, when the greedy heuristic or the LP needs it. The time to compute UFd+1\mathcal{U}^{d+1}_{\mathcal{F}} is reported for every setup in Tables T1–T10.


Q2. Sensitivity to ϵ\epsilon, inlier noise and the initial RANSAC bound nillbn_{il}^{lb}

  • nillbn_{il}^{lb}. The pruning thresholds (nillb−ρd+1−ρ)\binom{n_{il}^{lb}-\rho}{d+1-\rho} grow with nillbn_{il}^{lb}, so a weak initial bound prunes less. Algorithm 3 is designed to recover from this: after each pruning round it re-runs RANSAC on the much smaller pruned D\mathcal{D} and uses the greedy hitting set (∣D∣−∣Hg∣|\mathcal{D}|-|\mathcal{H}_g|) to tighten nillbn_{il}^{lb}, and pruning is repeated with each improved bound.
  • ϵ\epsilon. For the real-world experiments we use ϵ=1\epsilon = 1 pixel, a value commonly used in the literature.
  • Noise. The real-world data contain natural inlier noise from feature detection and matching.

Q3. Ablations for each stage

We have added a per-stage breakdown to the revised manuscript (Figure 3, and Tables T1–T10 in Appendix A.4), reporting for every setup the stage of Algorithm 3 that solved it and the optimality certificate that terminated it. In summary:

  • by the end of Stage I (point and subset pruning, RANSAC and greedy bound updates), 249 of 260 synthetic and 46 of 103 real setups (6 affine, 40 epipolar) are certified optimal;
  • by the end of Stage II (LP relaxation of MC3\mathcal{MC}3), all 260 synthetic and 58 of 103 real setups (10 affine, 48 epipolar) are certified optimal, without solving any MILP;
  • the final MILP fallback over the pruned D\mathcal{D} solves 43 of the remaining 45 real setups; on the 13 setups that the MILP over the full D\mathcal{D} also solves, the average MILP time drops from 29,928 s over the full D\mathcal{D} to 1.5 s over the pruned D\mathcal{D}.

Q4. Real affine matching: why 30 of 40 setups reach the MILP, and LP integrality versus greedy certificates

We refer the reviewer to Tables T5, T7 and T9 (Appendix A.4), which list every affine setup terminated in Stage I, II and III, respectively, together with its bounds and optimality certificate. In the 30 affine setups that reach Stage III, the greedy heuristic already finds a near-optimal hitting set, but its optimality could not be certified due to the loose counting lower bound and the large LP sizes.

How often each certificate closes the gap (Figure 3):

Fϵ(D)≠ϕ\mathcal{F}_\epsilon(\mathcal{D})\neq\phigreedy =nollb=n_{ol}^{lb}LP integralgreedy =⌈nollp⌉=\lceil n_{ol}^{lp}\rceilMILP
synthetic (260)102147650
affine (40)152228 (+2 unsolved)
epipolar (63)10307115

Q5. We have fixed the size of Tables 1–3 in the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.