Minimum relevant variables in linear system
The Min-RVLS problem (MINimum Relevant Variables in Linear System) is a problem in mathematical optimization. Given a linear program, it is required to find a feasible solution in which the number of non-zero variables is as small as possible.
The problem is known to be NP-hard and even hard to approximate.
Definition
A Min-RVLS problem is defined by:[1]
- A binary relation R, which is one of {=, ≥, >, ≠};
- An m-by-n matrix A (where m is the number of constraints and n the number of variables);
- An m-by-1 vector b.
The linear system is given by: A x R b. Depending on R, there are four different variants of this system: A x = b, A x ≥ b, A x > b, A x ≠ b.
The goal is to find an n-by-1 vector x that satisfies the system A x R b, and subject to that, contains as few as possible nonzero elements.
Special case
The problem Min-RVLS[=] was presented by Garey and Johnson,[2] who called it "minimum weight solution to linear equations". They proved it was NP-hard, but did not consider approximations.
Applications
The Min-RVLS problem is important in machine learning and linear discriminant analysis. Given a set of positive and negative examples, it is required to minimize the number of features that are required to correctly classify them.[3] The problem is known as the minimum feature set problem.[4]
References
- ^ "On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems". Theoretical Computer Science. 209 (1–2): 237–260. 1998-12-06. doi:10.1016/S0304-3975(97)00115-1. ISSN 0304-3975.
- ^ Johnson, David S.; Garey, M. R. (1979). "Computers and Intractability: A Guide to the Theory of NP-Completeness". www.semanticscholar.org. Retrieved 2019-01-07.
- ^ Koehler, Gary J. (1991-11-01). "Linear Discriminant Functions Determined by Genetic Search". ORSA Journal on Computing. 3 (4): 345–357. doi:10.1287/ijoc.3.4.345. ISSN 0899-1499.
- ^ Van Horn, Kevin S.; Martinez, Tony R. (1994-03-01). "The Minimum Feature Set Problem". Neural Netw. 7 (3): 491–494. doi:10.1016/0893-6080(94)90082-5. ISSN 0893-6080.