# Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 36 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [Maximum Feasible Subsystem Algorithms for Recovery of Compressively Sensed Speech](https://mlsanity.com/paper/2003.02927/) (2020)

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

- [Signature filtering: a lightweight enhancement for statistical watermark detection in large language models](https://mlsanity.com/paper/2606.18430/) (2026)

## Abstract (arXiv)

Finding the largest cardinality feasible subset of an infeasible set of linear constraints is the Maximum Feasible Subsystem problem (MAX FS). Solving this problem is crucial in a wide range of applications such as machine learning and compressive sensing. Although MAX FS is NP-hard, useful heuristic algorithms exist, but these can be slow for large problems. We extend the existing heuristics for the case of dense constraint matrices to greatly increase their speed while preserving or improving solution quality. We test the extended algorithms on two applications that have dense constraint matrices: binary classification, and sparse recovery in compressive sensing. In both cases, speed is greatly increased with no loss of accuracy.