- 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, is reset and rebuilt from all rho-subsets of D, and termination requires 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
(c) Termination of Algorithm 2
The reviewer is right about the submitted pseudocode. It rebuilt the candidate set from all -subsets of . A subset with count , 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 -subsets that occur in a current tuple of .
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 removes at least one tuple. The loop therefore ends after at most 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 -subsets over the current tuples and flags those with . This is the same set as the revised . It also stops if a pass removes no tuple. We will release the code.
Output on the six-point example (, , , ). We ran the implementation on this example, and it matches the step-by-step trace now in Appendix A.1.2:
- Algorithm 2.
- .
- The candidates are the six within-line pairs. Each has count , so and the loop ends after one pass. The cross-line pairs are never candidates.
- is unchanged and . 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 .
- The greedy hitting set over the 18 infeasible triples is , with .
- Certificate (i) of Proposition 4.1 therefore proves optimal. The algorithm returns (the line ) without solving an LP relaxation or a MILP. The other optimum, , 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 exactly on the pruned , 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 .
- Theorem 2.2:
- now requires , equivalently ;
- the proof handles solutions with at most 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 , 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 , 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.
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), b=(0,3,6) and ϵ=1, every pair of slabs is disjoint, so nil∗=1, yet MC3 admits a solution that deletes only one point. The claim in Section 2 that every subset of size at most d 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:
UFd+1=ϕ holds exactly when nil∗≥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+1 points in consensus, including all instances in our experiments. In the reviewer's example UFd+1=ϕ, since neither the triple nor any of the three pairs is feasible. That is precisely the excluded case.
Excluded case. UFd+1 is the first quantity Algorithm 3 computes. If it is empty, then nil∗≤d, and the optimum can be found easily by testing subsets of size d,d−1,… 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+1 inliers. What is new is the treatment of solutions with at most d inliers in MC3, the reviewer's concern. Such solutions can be feasible in MC3 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∗, while the complement of any optimal consensus set is feasible in MC3 with objective N−nil∗, none of them can be optimal. If desired, they can be excluded with the valid constraint ∑izi≤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ρ 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 ρ points were inliers of an optimal consensus set of size nil∗≥nillb, their count would be at least (d+1−ρnillb−ρ). Importantly, this condition is only used in Algorithm 2 to prune UFd+1 repeatedly, which then prunes D using the reduced UFd+1.
In the six-point example, S=(0,0),(3,10) has count 0<(11). 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:
Since Theorem 3.1, Corollary 3.4, the certificates of Proposition 4.1, and the exactness of MC3 on the pruned instance depend only on (P), all of them remain valid.