# Consensus Maximisation Using Influences of Monotone Boolean Functions

arXiv: https://arxiv.org/abs/2103.04200 · HTML: https://mlsanity.com/paper/2103.04200/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 6 Mar 2021.

## Builds on (most cited first, 7 of 7)

- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Quantum Robust Fitting](https://mlsanity.com/paper/2006.06986/) (2020)
- [Globally-Optimal Inlier Set Maximisation for Simultaneous Camera Pose and Feature Correspondence](https://mlsanity.com/paper/1709.09384/) (2017)
- [Consensus Maximization Tree Search Revisited](https://mlsanity.com/paper/1908.02021/) (2019)
- [Deterministic consensus maximization with biconvex programming](https://mlsanity.com/paper/1807.09436/) (2018)
- [Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision](https://mlsanity.com/paper/1909.12034/) (2019)

## Built on by (most cited first, 3 of 3)

- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [Maximum Consensus by Weighted Influences of Monotone Boolean Functions](https://mlsanity.com/paper/2112.00953/) (2021)

## Abstract (arXiv)

Consensus maximisation (MaxCon), which is widely used for robust fitting in computer vision, aims to find the largest subset of data that fits the model within some tolerance level. In this paper, we outline the connection between MaxCon problem and the abstract problem of finding the maximum upper zero of a Monotone Boolean Function (MBF) defined over the Boolean Cube. Then, we link the concept of influences (in a MBF) to the concept of outlier (in MaxCon) and show that influences of points belonging to the largest structure in data would generally be smaller under certain conditions. Based on this observation, we present an iterative algorithm to perform consensus maximisation. Results for both synthetic and real visual data experiments show that the MBF based algorithm is capable of generating a near optimal solution relatively quickly. This is particularly important where there are large number of outliers (gross or pseudo) in the observed data.