On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems

By Edoardo Amaldi, Viggo Kann. 1998

We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machine learning, operations research and pattern recognition. In the first class (Min ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the others. In the second class (Min RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both Min ULR and Min RVLS the four basic types of relational operators =, ⩾, > and ≠ are considered. While Min RVLS with equations was mentioned to be NP-hard in (Garey and Johnson, 1979), we established in (Amaldi; 1992; Amaldi and Kann, 1995) that min ULR with equalities and inequalities are NP-hard even when restricted to homogeneous systems with bipolar coefficients. The latter problems have been shown hard to approximate in (Arora et al., 1993). In this paper we determine strong bounds on the approximability of various variants of Min RVLS and min ULR, including constrained ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The various NP-hard versions turn out to have different approximability properties depending on the type of relations and the additional constraints, but none of them can be approximated within any constant factor, unless P = NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In particular, we disprove a conjecture of van Horn and Martinez (1992) regarding the existence of a polynomial-time algorithm to design linear classifiers (or perceptrons) that involve a close-to-minimum number of features.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

False data injection attacks against state estimation in electric power grids (2011, methodology): “This problem is 13:14 Y. Liu et al. the MIN RVLS= problem [Amaldi and Kann 1998]: Given a matrix A and a vector b, compute a vector x satisfying Ax =b such that x has as few nonzero elements as possible.”
Complete Search for Feature Selection in Decision Trees (2019, background): “The complete search of the lattice is known to be an NP-hard problem (Amaldi and Kann, c©2019 Salvatore Ruggieri.”
Deep Neural Networks for High Dimension, Low Sample Size Data (2017, background): “However, selecting the optimal subset of features is known to be NPhard [Amaldi and Kann, 1998].”
Structure‐preserving, stability, and accuracy properties of the energy‐conserving sampling and weighting method for the hyper reduction of nonlinear finite element dynamic models (2015, background): “Unfortunately, the optimization problem (22) is an NP-hard problem [34].”
Pose-based human action recognition via sparse representation in dissimilarity space (2014, background): “However the optimization problem defined in (1) is NP-hard combinatori al problem, and thus, in the general case, difficult even to approximate [2].”
A hybrid genetic algorithm for feature selection wrapper based on mutual information (2007, background): “Searching for the best m features out of the n available for classification task is known to be an NP-hard problem and the number of local minima can be quite large (Amaldi and Kann, 1998).”
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization (2009, background): “In a sense, this problem subsumes both the low rank matrix completion problem and the `-minimization problem, both of which are NP-hard and hard to approximate [23].”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, background): “The Maximum Agreement problem for halfspaces over R was shown to be NPhard to approximate within some constant factor in [1, 2].”
Dynamic Feature Selection for Online Action Recognition (2013, background): “However, as there are (2 - 1) possible combinations of d features, it is computationally unfeasible for large numbers of features as the problem is known to be NP-hard [12].”
Complexity theoretic limitations on learning halfspaces (2015, background): “Later on, the corresponding maximization problem was considered by several authors [5, 16, 23, 41, 38], culminating with Feldman, Gopalan, Khot and Ponnuswami [38] who showed that assuming that no quasi-polynomial time algorithm can solve NP hard problems, no efficient algorithm can distinguish samp”
Supervised classification and mathematical optimization (2013, background): “) The minimization of the zero-norm over a polyhedral set is an NP-Hard problem [2].”
Advances in kernel methods: support vector learning (1999, background): “…Vapnik, Volodya Vovk & Chris Watkins19 Combining Support Vector and Mathematical ProgrammingMethods for Classi cation 307Kristin P. Bennett20 Kernel Principal Component Analysis 327Bernhard Sch olkopf, Alex J. Smola & Klaus-Robert M uller 1998/08/25 16:31 viiReferences 353Index 373 1998/08/25 16:31”