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.
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
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.
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.
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.
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.
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.
Abstract Reasoning¶
A disciplined workflow is:
- Declare \(F\), \(A\), \(b\), relation \(R\), and encoding.
- Verify feasibility independently of sparsity.
- Produce an upper bound from any feasible support.
- Derive lower bounds from rank, combinatorial structure, dual reasoning, or relaxations.
- Choose exact, approximate, or heuristic solution status.
- Verify the returned vector and count support under a numerical zero tolerance declared in advance.
- Test alternate optima before interpreting selected coordinates.
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.
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 (83rd 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