Minimum Relevant Variables in a Linear System

Among all vectors satisfying a declared system of linear relations, select one with minimum support cardinality—the fewest nonzero variables—creating a generally NP-hard cardinality optimization rather than an ordinary continuous linear program.

Version

v2 · 2026-09-06 · History

Domain-specific #

2280

Origin domain

mathematical optimization

Subdomain

cardinality minimization

Aliases

Min-RVLS, Minimum nonzero-variable solution to linear relations, Minimum weight solution to linear equations

Core Idea

Minimum Relevant Variables in a Linear System (Min-RVLS) asks for a feasible solution that activates as few variables as possible. Given a matrix \(A\in F^{m\times n}\), vector \(b\in F^m\), and a declared componentwise relation \(R\) such as \(=\), \(\ge\), \(>\), or \(\ne\), solve

\[ \min_{x\in F^n}\|x\|_0 \quad\text{subject to}\quad Ax\;R\;b, \]

where \(\|x\|_0=|\{j:x_j\ne0\}|\) is support cardinality, not a norm in the usual analytic sense. The problem separates feasibility from parsimony: many vectors may satisfy the linear relations, and the objective chooses one using the smallest coordinate support.^[1]

The word “linear” describes the relation system, not the objective. Cardinality is discrete and nonconvex. Consequently, Min-RVLS is not an ordinary continuous linear program even though its constraints can be linear. Equality over \(GF(2)\) connects to minimum-weight codewords; classification formulations connect to minimum feature sets; sparse equation solving connects to compressed-sensing-like objectives but without the assumptions that make an \(\ell_1\) relaxation exact.

Structural Signature

The identity is:

declared coefficient domain + feasible linear relation system + coordinate support + cardinality objective + exact/approximate solution standard → sparsest feasible vector.

Mandatory roles are:

• The variable vector \(x\in F^n\).
• The linear data \((A,b)\).
• The relation family \(R\), applied componentwise and fixed for the variant.
• Feasibility: at least one vector satisfies the system or infeasibility is reported separately.
• Support: indices with nonzero coordinate values.
• The \(\ell_0\) objective: minimize support size, optionally with weights only when the variant says so.
• The coefficient/domain convention: reals, rationals, finite fields, integrality, and strict inequalities alter the problem.
• The solution standard: exact optimum, decision threshold \(k\), approximation ratio, or heuristic output.
• The complexity boundary: NP-hardness and inapproximability statements are tied to a precise variant and input encoding.
• The certificate relation: a proposed \(x\) is checked for all relations and its support counted; optimality needs a bound, exhaustive argument, or valid solver certificate.

Merely finding a sparse-looking feasible solution does not establish a minimum. Merely selecting a subset of variables without assigning values that satisfy the full system is feature screening, not a Min-RVLS solution.

What It Is Not

It is not Linear Programming in its unqualified continuous form. The feasible set may be polyhedral, but \(\|x\|_0\) is not linear or convex. Mixed-integer reformulations can encode activation with binary variables under valid bounds, but the reformulated problem is a MILP.

It is not least squares, which minimizes residual magnitude and may have dense solutions. It is not basis pursuit, which replaces cardinality by \(\|x\|_1\); that is a tractable relaxation with exact-recovery guarantees only under additional conditions. It is not minimum rank, where the decision object is a matrix and the counted resource is rank.

It is not Min-ULR, which starts from an infeasible system and minimizes the number of violated relations. Min-RVLS keeps all relations and minimizes nonzero variables. It is not Max-FLS, which selects the largest satisfiable constraint subset.

Scope of Application

The equality variant asks for the minimum-weight solution of \(Ax=b\). Garey and Johnson included the associated NP-hard problem in their catalog; Amaldi and Kann systematically analyzed equality and inequality/non-equality variants and approximation hardness.^[2][1]

In feature selection for linear discrimination, variables correspond to features and feasibility expresses correct classification constraints. Minimizing support chooses the smallest feature set for which some coefficient vector separates the examples. This is stronger than ranking variables independently because coefficients and feasibility are solved jointly.^[3]

In coding theory over \(GF(2)\), support size is Hamming weight. Suitable equality systems recover minimum-weight solution or shortest-codeword formulations. In sparse modeling, the same skeleton appears when a signal must be represented exactly by the fewest dictionary atoms.

The abstraction covers weighted or bounded variants only when the objective and bounds are stated. It does not absorb every sparse optimization problem: nonlinear constraints, group support, matrix rank, approximate residual tolerances, and structured sparsity are neighboring identities unless explicitly reduced to this form.

Clarity

“Relevant” is operational, not causal. A variable is relevant here because its coordinate is nonzero in the chosen feasible solution. A different optimal solution can use a different support. The problem does not prove that an input feature causes an outcome, nor that unused variables are scientifically irrelevant.

The relation \(\ne\) is nonconvex and behaves differently from \(=\) or \(\ge\). Strict inequalities also require care in finite-precision implementations. Complexity claims must specify whether coefficients are rationally encoded, whether the field is finite or real, and whether approximation is multiplicative when the optimum can be zero.

The common surrogate

\[ \min\|x\|_1\quad\text{subject to }Ax=b \]

is not definitional. It can return the same sparse vector under null-space, coherence, or restricted-isometry conditions, but can also return a denser solution. A successful relaxation is a method for some instances, not identity of the problem.

Manages Complexity

Min-RVLS turns parsimony into an explicit resource count. It exposes the difference between satisfying all relations and doing so with a minimal active coordinate set. That lets feature selection, sparse explanation, and codeword search share one optimization skeleton.

The abstraction also prevents solver confusion. If cardinality is the objective, a continuous LP solver cannot optimize it directly. One must use combinatorial search, mixed-integer modeling with justified bounds, branch-and-bound, cutting planes, relaxations, greedy procedures, or domain-specific algorithms—and label heuristic versus certified results.

Complexity results manage expectations: poor worst-case approximability means that a universally reliable near-optimal polynomial algorithm is unlikely under the cited assumptions.^[4] It does not say every practical instance is hard, nor that structure-specific recovery is impossible.

Abstract Reasoning

A disciplined workflow is:

1. Declare \(F\), \(A\), \(b\), relation \(R\), and encoding.
2. Verify feasibility independently of sparsity.
3. Produce an upper bound from any feasible support.
4. Derive lower bounds from rank, combinatorial structure, dual reasoning, or relaxations.
5. Choose exact, approximate, or heuristic solution status.
6. Verify the returned vector and count support under a numerical zero tolerance declared in advance.
7. Test alternate optima before interpreting selected coordinates.

For a small equality system, support-one feasibility can be checked by asking whether \(b\) is a scalar multiple of one column of \(A\). If not, test pairs of columns, then triples. This support-layer search gives a constructive exact method for small \(n\) and clarifies why combinatorial growth occurs.

Knowledge Transfer

Columns of \(A\) can map to candidate features, dictionary atoms, codeword positions, interventions, or explanatory variables. Nonzero coefficients map to selected items; linear feasibility maps to exact reconstruction, separation, or relation satisfaction. The support-count objective transfers unchanged.

Transfer fails when “few” refers to constraints, groups, ranks, or approximate error rather than coordinates. Min-ULR counts violated rows; group lasso counts blocks; matrix completion controls rank; sparse regression often permits residual error. These require remapping the counted object and may be different abstractions.

Examples

One-column solution. If \(b=3a_7\), where \(a_7\) is column 7 of \(A\), then \(x_7=3\) and all other coordinates zero is feasible with support one. If \(b\ne0\), support zero is impossible, so this is certified optimal.

Minimum feature separator. Each coordinate is a measured feature and inequalities require positive examples to receive positive score and negative examples negative score. A sparsest feasible coefficient vector identifies a smallest jointly sufficient linear feature set, subject to the dataset and margin convention.

Binary code. Over \(GF(2)\), support is Hamming weight. Seeking a nonzero vector satisfying parity constraints with minimum weight maps to a shortest-codeword family.

\(\ell_1\) mismatch. A basis-pursuit solution may be easy to compute but use more nonzero coordinates than the true cardinality optimum. It is a relaxation result and must not be reported as exact Min-RVLS without a recovery certificate.

Non-example. Dropping the hardest constraints until a dense vector becomes feasible solves a constraint-selection problem, not Min-RVLS.

Structural Tensions

• Exact sparsity versus tractability: the literal objective produces combinatorial hardness.
• Cardinality versus numerical tolerance: floating-point near-zero values complicate support counting.
• Prediction versus interpretability: smallest training support can be unstable or generalize poorly.
• One optimum versus many supports: alternate sparse solutions weaken variable-level conclusions.
• Relaxation speed versus exact identity: \(\ell_1\) is useful but not automatically equivalent.
• General hardness versus structured recovery: worst-case results coexist with easy special families.

Structural–Framed Character

The mathematical identity is structural once domain, relation, and objective are declared. Framing enters through which variables count, whether approximate feasibility is allowed, and the practical value assigned to sparsity. Optimality itself is not subjective.

Structural Core vs. Domain Accent

The core is Optimization over a feasible set with a minimum-resource objective. The domain accent is a linear relation system and coordinate-support cardinality, plus variant-specific hardness and certificates. Removing those yields generic optimization or parsimony, so the node is domain-specific.

Instantiates / Related Primes

Optimization is the proposed immediate parent. The choice set is \(F^n\), feasibility is \(AxRb\), and the objective is \(\|x\|_0\). Linear Programming supplies part of the constraint structure but not the objective. Minimum Sufficient Capability is analogically related to activating few coordinates, not a strict mathematical parent.

One prospective strict edge to prime:optimization is queued. No live DAG mutation is authorized.

Relationships to Other Abstractions

Current abstraction Minimum Relevant Variables in a Linear System Domain-specific

Parents (1) — more general patterns this builds on

• Minimum Relevant Variables in a Linear System is a kind of Optimization Prime

  Optimization is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Minimum Relevant Variables in a Linear System → Optimization

Neighborhood in Abstraction Space

Minimum Relevant Variables in a Linear System sits in a sparse region of the domain-specific corpus (83^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Matrix Pencil — 0.82
• Quadratic Equation — 0.82
• Limited-Memory BFGS — 0.82
• Special Ordered Set — 0.81
• Fourier–Motzkin Elimination — 0.81

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

• Linear Programming: linear objective over linear constraints.
• Basis Pursuit / \(\ell_1\) minimization: convex surrogate.
• Least Squares: residual minimization.
• Min-ULR: minimizes violated relations.
• Max-FLS: maximizes satisfiable constraint subset.
• Minimum Rank: counts independent matrix dimensions.
• Feature ranking: scores coordinates independently rather than solving joint feasibility.
• Causal variable relevance: not established by nonzero support.

References

[1] Edoardo Amaldi and Viggo Kann, “On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems,” Theoretical Computer Science 209 (1998): 237–260, DOI 10.1016/S0304-3975(97)00115-1. Primary definition and complexity analysis. registry ↩a ↩b

[2] Michael R. Garey and David S. Johnson, Computers and Intractability, W. H. Freeman, 1979, ISBN 9780716710448. Canonical source for the minimum-weight solution-to-linear-equations hardness problem. registry ↩

[3] Kevin S. Van Horn and Tony R. Martinez, “The Minimum Feature Set Problem,” Neural Networks 7, no. 3 (1994): 491–494, DOI 10.1016/0893-6080(94)90082-5. registry ↩

[4] Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk, “The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations,” Journal of Computer and System Sciences 54 (1997): 317–331, DOI 10.1006/jcss.1997.1472. registry ↩