Jump to content

Minimum relevant variables in linear system

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 11:42, 7 January 2019 (→Applications). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

MINimum Relevant Variables in Linear System (Min-RVLS) 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. It is assumed to be feasible (i.e., satisfied by at least one x). 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. An algorithm that approximates Min-RVLS within a factor of could substantially reduce the number of training samples required to attain a given accuracy level. [4]

In MINimum Unsatisfied Linear Relations (Min-ULR), we are given a binary relation R and a linear system A x R b, which is now assumed to be infeasible. The goal is to find a vector x that violates as few relations as possible, while satisfying all the others.

In the complementary problem MAXimum Feasible Linear Subystem (Max-FLS), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously.[5]

  • Max-FLS[≠] can be solved in polynomial time.
  • Max-FLS[=] is NP-hard even with homogeneous systems and bipolar coefficients.
  • . With integer coefficients, it is hard to approximate within . With coefficients over GF[q], it is q-approximable.
  • Max-FLS[>] and Max-FLS[≥] are NP-hard even with homogeneous systems and bipolar coefficients. They are 2-approximable, but they cannot be approximated within any smaller constant factor.

References

  1. ^ "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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ "The complexity and approximability of finding maximum feasible subsystems of linear relations". Theoretical Computer Science. 147 (1–2): 181–210. 1995-08-07. doi:10.1016/0304-3975(94)00254-G. ISSN 0304-3975.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minimum_relevant_variables_in_linear_system&oldid=877233946"