Skip to content

Basis Extraction from a Spanning Set

Procedure — instantiates Independent Generating Set Design

Given a redundant set that already covers the space, prunes it to a maximal independent subset that still covers everything — turning a pile of generators into an actual basis.

Basis Extraction from a Spanning Set starts where coverage is already guaranteed — you hold a collection you know spans the space — and removes the redundancy that keeps it from being a basis. Its defining premise is that the hard half of the problem (completeness) is already solved; the job is to strip out every generator that adds no new direction until what remains is independent and minimal. This is what separates it from Data-Adapted Basis Learning, which invents generators from data, and from Change-of-Basis Matrix, which converts between two bases that already exist. Extraction only ever selects from the pool it is handed.

Example

A product-analytics team tracks 30 KPIs that together plainly cover "business health" — the set spans — but most are entangled: total revenue, revenue per seat, seat count, monthly recurring revenue, and churn-adjusted revenue all move together. Extraction walks the list in priority order and keeps a KPI only if it enlarges the span already covered by the ones kept so far; the rest are discarded as reconstructible from the survivors. The team lands on a minimal, independent basis of nine KPIs from which the other twenty-one can be recomputed exactly. Now every dashboard number carries unique meaning, and no two metrics silently encode the same degree of freedom.

How it works

The candidates are ordered by priority or quality, and the procedure sweeps through them greedily: each generator is tested for independence against the accumulating kept set — does it reach a direction not yet spanned? — and is retained if it does, dropped if it does not. The sweep stops once the kept set's span equals the target space. What remains is provably a basis: independent, because every member added a new dimension when it entered, and spanning, because every discarded member was already covered. This is the constructive form of the fact that every spanning set contains a basis.

Tuning parameters

  • Candidate ordering — which generators get first claim on the basis. Different orderings yield different (equally valid) bases with different meanings and different conditioning, so ordering is a real editorial choice.
  • Independence tolerance — exact vs. numerical: whether a nearly dependent generator counts as dependent. Tighten it and you keep near-duplicates; loosen it and you may drop something the space needs.
  • Selection strategy — plain greedy vs. pivoted vs. an optimization that also targets conditioning or interpretability; changes which minimal set you reach.
  • Target coverage — the full space, or a tolerance-defined subspace ("keep just enough generators to reconstruct 99% of observed objects").

When it helps, and when it misleads

Its strength is dissolving hidden redundancy that inflates the apparent dimension of a problem — after extraction, coordinates are unique and the true number of degrees of freedom is visible. It is the cleanest route from "we have lots of overlapping levers" to "here are the independent ones."

Its honest limitation is that the extracted basis is not unique: it depends on the ordering and the tolerance, so "the basis" is really "a basis this policy produced."[1] That opens the door to the classic misuse — choosing an ordering that keeps the favoured generators and prunes the inconvenient ones, manufacturing a basis to fit a conclusion already reached. The discipline is to fix the ordering rule and tolerance before extracting and to record them, then confirm that the discarded generators genuinely reconstruct from the kept set.

How it implements the components

Basis Extraction realizes the constructive core of the archetype — the components that turn a redundant pool into a genuine basis:

  • candidate_generator_pool — the input spanning set it prunes; extraction operates entirely within this given collection.
  • span_and_coverage_criterion — at every step it verifies that dropping a generator preserves full coverage.
  • generator_independence_criterion — the keep/drop test is the independence criterion applied one generator at a time.
  • minimality_and_pruning_rule — the pruning down to a non-redundant, minimal set is the procedure's whole output.

It does not report a rank/dimension figure as a standalone diagnostic (that framing is Experimental Design-Matrix Rank Check), assess the survivors' numerical stability (Basis Conditioning and Perturbation Audit), or create new generators (Data-Adapted Basis Learning).

Notes

Extraction guarantees a basis — independent, minimal, spanning — but not a good one. The survivors may be badly conditioned or semantically awkward, because the procedure optimizes for non-redundancy, not for stability or interpretability. Those are separate concerns, handed to the conditioning audit and to interpretability preferences respectively. Algorithmically, pivoted row reduction and rank-revealing QR are the workhorses that carry out the independence test at scale.

References

[1] That any spanning set contains a basis, and that all such bases have the same size, is the Steinitz exchange lemma — the theorem underwriting both the procedure's correctness and its non-uniqueness. ↩