Faster Maximum Feasible Subsystem Solutions for Dense Constraint Matrices
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationCompressive SensingSimilar Papers 제목 키워드 기반
Novel General Active Reliability Redundancy Allocation Problems and Algorithm
The traditional (active) reliability redundancy allocation problem (RRAP) is used to maximize system reliability by determining the redundancy and reliability variables in each subsystem to satisfy the volume, cost, and …
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interleave successful techniques from related …
Source Localization of an Unknown Transmission in Dense Multipath Environments
Accurately estimating the position of a wireless emitter in a multipath environment based on samples received at various base stations (in known locations) has been extensively explored in the literature. Existing approa…
PositionSMART: Scalable Multi-Agent Reasoning and Trajectory Planning in Dense Environments
Multi-vehicle trajectory planning is a non-convex problem that becomes increasingly difficult in dense environments due to the rapid growth of collision constraints. Efficient exploration of feasible behaviors and resolu…
Distributed OptimizationReinforcement LearningCollision AvoidanceTrajectory PlanningSubsystem decomposition and state estimation of nonlinear processes with implicit time-scale multiplicity
In this work, we propose a subsystem decomposition approach and a distributed estimation scheme for a class of implicit two-time-scale nonlinear systems. Taking the advantage of the two-time-scale separation, these proce…
Chemical ProcessState Estimation