Struct Reduction

Source

pub struct Reduction { /* private fields */ }

Expand description

A decorrelated ILS problem: the transformation, the factorisation and the transformed float vector the search runs on.

Building one is the expensive half of LAMBDA and depends on Q alone, so a caller holding Q fixed across epochs — the usual case, since the ambiguity covariance changes far more slowly than the float estimate — builds it once.

Implementations§

Source §

impl Reduction

Source

pub fn new(float: &[f64], covariance: &[f64]) -> Result<Self, LambdaError>

Decorrelate the problem given by the float ambiguities float and their covariance covariance (row-major, n × n).

§Errors

LambdaError if the dimensions disagree, the problem is empty, an entry is not finite, the covariance is not symmetric, or it is not positive definite.

Source

pub const fn len(&self) -> usize

The number of ambiguities.

Source

pub const fn is_empty(&self) -> bool

Whether there are no ambiguities. Never true — Reduction::new refuses an empty problem — and present because a type with len and without is_empty is a trap for the reader.

Source

pub fn transformation(&self) -> &[f64]

The unimodular transformation Z, row-major, with z = Zᵀa.

Integer-valued by construction: every entry is an exact integer stored in an f64, which is lossless well past any magnitude a GNSS reduction produces.

Source

pub fn conditional_variances(&self) -> &[f64]

The conditional variances d̄ of the decorrelated problem, in index order.

Their spread is what the reduction exists to shrink: the ratio of the largest to the smallest is the search’s difficulty, and on GNSS covariances the reduction lowers it by orders of magnitude.

Source

pub fn bootstrap(&self) -> Candidate

The bootstrapped (Babai) estimate: round the last ambiguity, condition the rest on it, work backwards, and map back through Z.

Cheap — no search — and on a reduced problem usually the ILS solution, but not guaranteed to be. Use it where an answer is needed within a fixed budget, or as the starting point it is for Reduction::search.

Source

pub fn search(&self, count: usize) -> Result<Vec<Candidate>, LambdaError>

The count best integer vectors, in increasing order of the ILS objective.

The first is the integer least-squares solution. The second is what the standard ratio test needs, which is why asking for two is the usual call. Returns fewer than count only when count exceeds the number of integer vectors that exist, which for n ≥ 1 it does not.

Enumerates in the Schnorr–Euchner order — at every level the nearest integer first, then alternating outwards — so the first full vector found is the bootstrapped estimate and the ellipsoid can be shrunk to it immediately. Once count candidates are held, the bound is the worst of them, and the search is exhaustive within that bound: any vector it discards is provably worse than every one it kept.

count is therefore also a work bound — the ellipsoid stays unbounded until that many candidates are held, so asking for a large count asks for a large enumeration.

The projections are carried between levels rather than rebuilt at each node, after Ghasemmehdi and Agrell (Faster projection in sphere decoding, IEEE Trans. Inf. Theory 57(6):3530–3536, 2011, §III-B). A node revisited after a climb costs one multiply–add per level the climb passed through instead of a fresh inner product over every level above it, which is what LAMBDA 4.0 adopts and where its speed-up at high dimension comes from.