Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices

DOI10.1016/J.COR.2021.105633MaRDI QIDQ6360345arXivFDO

Authors Fereshteh Fakhar Firouzeh, John W. Chinneck, Sreeraman Rajan

Publication date 10 February 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.COR.2021.105633

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59)

arXiv classification

cs.LG math.OC

Abstract: 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.

This page was built for publication: Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360345)