Skip to content

Independent-Seed Basis Extension

Basis-completion method — instantiates Independent Generating Set Design

Grows a partial, already-independent set into a complete basis by repeatedly adding only directions the current set cannot already reach.

Independent-Seed Basis Extension starts from a seed — a set of independent vectors you are committed to keeping — and grows it into a full basis without disturbing the seed. Its defining move is directional: it only ever adds, and it admits a candidate exactly when that candidate points somewhere the current set cannot already reach. Everything the accepted vectors can build is off-limits as a new generator; only a genuinely new direction earns a slot. The process halts the moment the set spans the whole space. This is the mirror image of trimming an over-complete set down to a basis — here the set is too small, and the work is to complete it while protecting the vectors that had to stay.

Example

A display engineer is designing a wide-gamut screen and is required to keep two specific primary lights already chosen for cost and efficiency — that is the seed. But two primaries only mix the colors on the line between them; they span a mere sliver of what the eye can see. To reproduce the full range of human color, the engineer must add primaries that lie outside the reach of the ones already chosen. A third candidate LED is auditioned: does it produce a color that cannot be matched by any mixture of the first two? If yes, it adds a new dimension of color and is accepted; if it merely reproduces a shade already mixable, it is redundant and rejected.

With a third independent primary admitted, the set spans the full three-dimensional color space of human vision, and the extension stops — the seed survived, and every color is now reachable as a combination of the chosen primaries.

How it works

  • Fix the seed. Lock in the independent vectors that must be kept; they are never pruned.
  • Audition candidates. For each candidate from the pool, test whether it is independent of the current span — does it raise the reach of the set, or is it already a combination of accepted vectors?
  • Admit or discard, then check coverage. Accept independent candidates, discard dependent ones, and stop when the set spans the target space (its size reaches the space's dimension).

What distinguishes it from its neighbours is the protected seed and the grow-until-complete stopping rule: it is completion, not selection or pruning.

Tuning parameters

  • Seed choice — which vectors are locked in up front; they constrain every later addition, and their quality propagates into the finished basis.
  • Candidate source and ordering — the pool drawn from and the order auditioned; first-fit fills the gap fast, best-fit fills it well.
  • Independence tolerance — how much genuinely new reach a candidate must add to count as independent; strict rejects near-dependent noise, loose risks admitting it.
  • Target dimension — the span being completed to — the full space, or a known subspace of dimension r.
  • Conditioning preference — among independent candidates, favouring those that keep the growing basis well-conditioned rather than merely non-redundant.

When it helps, and when it misleads

Its strength is that it honours must-keep directions — a legacy component, an interpretable axis, a physically fixed primary — and still guarantees completeness. The Steinitz exchange lemma[1] promises that any independent seed can be extended to a basis, and that every basis of the space has the same size, so the procedure always succeeds and terminates at exactly the space's dimension.

It misleads when the seed or the tolerance is poor. A near-dependent seed forces awkward, ill-conditioned completions; a myopic greedy fill can reach full span yet leave a badly conditioned basis; and a loose independence tolerance can admit a noise-level "direction," inflating the apparent dimension past the true one. The classic misuse is extending beyond the real dimension by accepting directions that are independent only within round-off. The discipline is to pair the independence test with a conditioning check and to confirm the final count equals the known dimension of the space.

How it implements the components

Independent-Seed Basis Extension fills the completion side of the archetype:

  • candidate_generator_pool — it consumes a pool of candidate directions, drawing completions from it one at a time.
  • generator_independence_criterion — the admit/reject test is the independence criterion, applied to each candidate against the growing set.
  • span_and_coverage_criterion — the stopping rule is coverage: keep adding until the set spans the target space.

It does not prune redundancy from an over-complete set — that inverse is Basis Extraction from a Spanning Set — nor orthonormalize its output (Gram–Schmidt Orthonormalization), nor set the numerical rank tolerance under noise (Singular-Value Rank Diagnosis).

Notes

Extension and extraction are duals: this mechanism grows a too-small independent set up to a basis, while Basis Extraction from a Spanning Set trims a too-large spanning set down to one. They meet in the middle at a basis, and the independence test at the heart of extension is often run as a Gram–Schmidt step — a candidate is accepted precisely when its orthogonal remainder against the current set is nonzero.

References

[1] The Steinitz exchange lemma: any linearly independent set in a finite-dimensional space can be extended to a basis, and every basis of that space has the same number of elements. It is the guarantee that completion always succeeds and terminates at the space's dimension. ↩