Estimators#

All estimators inherit from BaseEstimator and expose a single iterate(A, b) → x interface.

Base Class#

Abstract base class for all online parameter estimators.

Every estimator in TAG-K follows the same iterate(A, b) -> theta protocol, making them interchangeable in simulation loops and benchmarks.

class online_estimators.estimators.base.BaseEstimator(num_params)[source]#

Bases: ABC

Abstract base class for online parameter estimators.

All estimators solve the overdetermined linear system A theta ~= b incrementally – each call to iterate() ingests a new batch of rows and returns the current best estimate of theta.

Parameters:

num_params (int) – Dimension of the parameter vector theta.

abstractmethod iterate(A, b)[source]#

Ingest a new measurement batch and return the updated estimate.

Parameters:

  • A (np.ndarray, shape (m, n)) – Measurement (regressor) matrix for this batch.

  • b (np.ndarray, shape (m,)) – Observation vector for this batch.

Returns:

Updated parameter estimate theta_hat.

Return type:

np.ndarray, shape (n,)

Recursive Least Squares#

Recursive Least Squares (RLS) estimator with exponential forgetting.

The RLS algorithm minimises a weighted least-squares cost where older measurements are exponentially down-weighted via a forgetting factor lam in (0, 1]. Smaller lam discounts old data more aggressively, yielding faster adaptation at the expense of higher variance.

class online_estimators.estimators.rls.RLS(num_params, theta_hat=None, forgetting_factor=0.3, c=1000.0)[source]#

Bases: BaseEstimator

Recursive Least Squares with exponential forgetting.

The update equations are:

\[\begin{split}S_k &= A_k P_{k-1} A_k^T + \lambda I \\ K_k &= P_{k-1} A_k^T S_k^{-1} \\ \hat\theta_k &= \hat\theta_{k-1} + K_k (b_k - A_k \hat\theta_{k-1}) \\ P_k &= (P_{k-1} - K_k A_k P_{k-1}) / \lambda\end{split}\]

When the C++ extension online_estimation is installed, the iterate method delegates to a compiled implementation for better performance.

Parameters:

  • num_params (int) – Dimension of the parameter vector.

  • theta_hat (np.ndarray or None) – Initial parameter estimate. Defaults to zero.

  • forgetting_factor (float) – Forgetting factor lam. Typical range: [0.2, 1.0].

  • c (float) – Initial covariance scaling – P_0 = c * I.

Examples

>>> import numpy as np
>>> from online_estimators.estimators import RLS
>>> est = RLS(num_params=3, forgetting_factor=0.9)
>>> A = np.random.randn(6, 3)
>>> b = A @ np.array([1.0, 2.0, 3.0])
>>> theta = est.iterate(A, b)
iterate(A, b)[source]#

Perform one RLS update with a batch of measurements.

Parameters:

  • A (np.ndarray, shape (m, n)) – Regressor matrix.

  • b (np.ndarray, shape (m,)) – Observation vector.

Returns:

Updated parameter estimate.

Return type:

np.ndarray, shape (n,)

Kalman Filter#

Kalman Filter for parameter estimation (flipped model).

In the “flipped-model” formulation the parameters are treated as the hidden state and the measurements provide an observation equation b = A theta + v. A constant-dynamics model theta_{k+1} = theta_k + w is assumed, making this a simple parameter-tracking filter.

class online_estimators.estimators.kf.KF(num_params, process_noise, measurement_noise, theta_hat=None, c=10.0)[source]#

Bases: BaseEstimator

Kalman Filter for online parameter estimation.

State model: theta_{k+1} = theta_k + w_k, with w_k ~ N(0, Q)

Observation: b_k = A_k theta_k + v_k, with v_k ~ N(0, R)

When the C++ extension online_estimation is installed, the iterate method delegates to a compiled implementation for better performance.

Parameters:

  • num_params (int) – Dimension of the parameter vector.

  • process_noise (np.ndarray, shape (n, n)) – Process noise covariance Q.

  • measurement_noise (np.ndarray, shape (m, m)) – Measurement noise covariance R. Must match the number of rows in A at each call.

  • theta_hat (np.ndarray or None) – Initial estimate. Defaults to zero.

  • c (float) – Initial covariance scaling – P_0 = c * I.

Examples

>>> import numpy as np
>>> from online_estimators.estimators import KF
>>> n, m = 4, 6
>>> kf = KF(n, process_noise=1e-3*np.eye(n),
...         measurement_noise=1e-4*np.eye(m))
>>> A = np.random.randn(m, n)
>>> b = A @ np.ones(n) + 0.01 * np.random.randn(m)
>>> theta = kf.iterate(A, b)
iterate(A, b)[source]#

Perform one predict-update cycle.

Parameters:

  • A (np.ndarray, shape (m, n)) – Observation matrix.

  • b (np.ndarray, shape (m,)) – Measurement vector.

Returns:

Updated parameter estimate.

Return type:

np.ndarray, shape (n,)

Randomized Kaczmarz Family#

Randomized Kaczmarz (RK) and its preconditioned/augmented variants.

The basic Randomized Kaczmarz algorithm solves Ax = b by repeatedly projecting onto randomly selected hyperplanes defined by individual rows of A. Rows are sampled proportional to their squared norm.

This module provides:

  • RK – vanilla randomized Kaczmarz

  • TARK – tail-averaged RK (Polyak averaging over the second half)

  • RK_ColScaled – column-scaled (right-preconditioned) RK

  • RK_Equi – Ruiz-equilibrated RK (left + right preconditioning)

  • RK_Tikh – Tikhonov-augmented RK (ridge-like regularisation)

  • RK_EquiTikh – Ruiz equilibration + Tikhonov augmentation

online_estimators.estimators.rk.ruiz_equilibrate(A, iters=5, eps=1e-12)[source]#

Ruiz equilibration: iterative row/column scaling.

Returns (B, Dr, Dc) such that B = diag(Dr) A diag(Dc) is approximately doubly-stochastic in row/column norms.

Parameters:

  • A (np.ndarray, shape (m, n))

  • iters (int) – Number of Ruiz iterations. 5 is usually sufficient.

  • eps (float) – Small constant for numerical stability.

Return type:

tuple[ndarray, ndarray, ndarray]

Returns:

  • B (np.ndarray, shape (m, n)) – Equilibrated matrix.

  • Dr (np.ndarray, shape (m,)) – Row scaling factors.

  • Dc (np.ndarray, shape (n,)) – Column scaling factors.

class online_estimators.estimators.rk.RK(num_params, x0=None)[source]#

Bases: BaseEstimator

Classic Randomized Kaczmarz.

At each call, performs m inner Kaczmarz sweeps (one per row in expectation) with row-norm-proportional sampling.

When the C++ extension online_estimation is installed, the iterate method delegates to a compiled implementation for better performance.

Parameters:

  • num_params (int) – Dimension of theta.

  • x0 (np.ndarray or None) – Initial iterate. Defaults to zero.

Examples

>>> import numpy as np
>>> from online_estimators.estimators import RK
>>> rk = RK(num_params=5)
>>> A = np.random.randn(20, 5)
>>> b = A @ np.ones(5)
>>> theta = rk.iterate(A, b)
seed_rng(seed)[source]#

Seed the internal random engine for reproducibility.

Parameters:

seed (int) – Seed value.

Return type:

None

iterate(A, b, eps=1e-12)[source]#

Run one epoch of randomized Kaczmarz sweeps.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float) – Numerical stability constant.

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.rk.TARK(num_params, x0=None, default_burnin=0)[source]#

Bases: BaseEstimator

Tail-Averaged Randomized Kaczmarz.

Identical to RK but returns the Polyak average of the iterates after a configurable burn-in period.

When the C++ extension online_estimation is installed, the iterate method delegates to a compiled implementation for better performance. Note that the C++ backend uses the burnin value from construction and ignores the per-call burnin argument.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • default_burnin (int) – Default burn-in value used by the C++ backend when available.

Examples

>>> from online_estimators.estimators import TARK
>>> est = TARK(num_params=3)
>>> theta = est.iterate(A, b, burnin=5)
seed_rng(seed)[source]#

Seed the internal random engine for reproducibility.

Parameters:

seed (int) – Seed value.

Return type:

None

iterate(A, b, burnin=0, eps=1e-12)[source]#

Run one epoch and return the tail-averaged iterate.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • burnin (int) – Number of initial sweeps to discard before averaging. Ignored when the C++ backend is active (uses constructor value).

  • eps (float) – Numerical stability constant.

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.rk.RK_ColScaled(num_params, x0=None)[source]#

Bases: BaseEstimator

Randomized Kaczmarz with column scaling (right preconditioning).

Scales columns of A by their standard deviation before running Kaczmarz, then maps the solution back. This is effective when columns have very different magnitudes.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

iterate(A, b, eps=1e-12)[source]#

Run column-scaled Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.rk.RK_Equi(num_params, x0=None, ruiz_iters=5)[source]#

Bases: BaseEstimator

Randomized Kaczmarz with Ruiz equilibration.

Applies iterative row/column (Ruiz) scaling before Kaczmarz to improve the condition number of A.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • ruiz_iters (int) – Number of Ruiz balancing iterations.

iterate(A, b, eps=1e-12)[source]#

Run Ruiz-equilibrated Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.rk.RK_Tikh(num_params, x0=None, lam=None, lam_scale=1e-05)[source]#

Bases: BaseEstimator

Randomized Kaczmarz on the Tikhonov-augmented system.

Appends sqrtlam * I rows and zero RHS to the system, turning Kaczmarz into an implicit ridge regression.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • lam (float or None) – Explicit regularisation parameter. If None, it is set automatically as lam_scale * ||A||_F^2 / m.

  • lam_scale (float) – Scale factor for the automatic lam.

iterate(A, b, eps=1e-12)[source]#

Run Tikhonov-augmented Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.rk.RK_EquiTikh(num_params, x0=None, ruiz_iters=5, lam=None, lam_scale=0.001)[source]#

Bases: BaseEstimator

RK with both Ruiz equilibration and Tikhonov augmentation.

Combines the benefits of condition-number improvement (Ruiz) and regularisation (Tikhonov).

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • ruiz_iters (int)

  • lam (float or None)

  • lam_scale (float)

iterate(A, b, eps=1e-12)[source]#

Run Ruiz-equilibrated, Tikhonov-augmented Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

Greedy Randomized Kaczmarz Family#

Greedy Randomized Kaczmarz (GRK) and its variants.

GRK improves upon vanilla Randomized Kaczmarz by selecting rows with large residual-to-norm ratios, concentrating updates where they reduce the error most. An adaptive threshold eps_k is computed each iteration to define the “greedy” working set.

Variants in this module:

  • GRK – base greedy RK

  • TAGK – GRK + Polyak tail-averaging

  • GRK_Tikh – GRK on the Tikhonov-augmented system

  • TAGK_Tikh – GRK + Tikhonov + tail-averaging

class online_estimators.estimators.grk.GRK(num_params, x0=None, default_tol=0.0001)[source]#

Bases: BaseEstimator

Greedy Randomized Kaczmarz (GRK).

Selects rows whose per-row residual is large relative to the global residual, then samples from this “greedy set” with residual-proportional probabilities.

When the C++ extension online_estimation is installed, the iterate method delegates to a compiled implementation for better performance. The C++ backend does not support the n_iters, x0, tol, or rng arguments – those calls fall back to pure Python automatically.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • default_tol (float) – Default tolerance used by the C++ backend when available.

References

Bai, Z. & Wu, W. “On greedy randomized Kaczmarz method for solving large sparse linear systems.” SIAM J. Sci. Comput., 40(1), 2018.

Examples

>>> from online_estimators.estimators import GRK
>>> grk = GRK(num_params=10)
>>> theta = grk.iterate(A, b)
seed_rng(seed)[source]#

Seed the internal random engine for reproducibility.

Parameters:

seed (int) – Seed value.

Return type:

None

iterate(A, b, n_iters=None, x0=None, tol=0.0, rng=None)[source]#

Run n_iters greedy Kaczmarz iterations.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • n_iters (int or None) – Number of iterations. Defaults to m.

  • x0 (np.ndarray or None) – Override starting point for this call.

  • tol (float) – Early-stop tolerance on ||r||^2.

  • rng (np.random.Generator or None)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.grk.TAGK(num_params, x0=None, burnin=0, default_tol=0.0001)[source]#

Bases: BaseEstimator

Greedy RK with Polyak tail-averaging.

Same greedy row selection as GRK, but returns the average of iterates collected after a burn-in phase.

When the C++ extension online_estimation is installed and no per-call overrides are requested, the iterate method delegates to the C++ TAGK implementation for better performance.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • burnin (int) – Iterations to skip before starting the running average.

  • default_tol (float) – Default tolerance used by the C++ backend when available.

seed_rng(seed)[source]#

Seed the internal random engine for reproducibility.

Parameters:

seed (int) – Seed value.

Return type:

None

iterate(A, b, n_iters=None, x0=None, tol=0.0, rng=None)[source]#

Run greedy Kaczmarz with tail-averaging.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • n_iters (int or None)

  • x0 (np.ndarray or None)

  • tol (float)

  • rng (np.random.Generator or None)

Returns:

Tail-averaged iterate.

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.grk.GRK_Tikh(num_params, x0=None, lam=None, lam_scale=1e-05)[source]#

Bases: BaseEstimator

Greedy RK on the Tikhonov-augmented system.

Appends sqrtlam * I rows to A for implicit regularisation, then applies greedy row selection.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • lam (float or None)

  • lam_scale (float)

iterate(A, b, n_iters=None, x0=None, tol=0.0, rng=None)[source]#

Run Tikhonov-augmented greedy Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • n_iters (int or None)

  • x0 (np.ndarray or None)

  • tol (float)

  • rng (np.random.Generator or None)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.grk.TAGK_Tikh(num_params, x0=None, lam=None, lam_scale=0.001)[source]#

Bases: BaseEstimator

Greedy RK + Tikhonov augmentation + tail-averaging.

This is the TAG-K algorithm: combines greedy row selection, Tikhonov regularisation, and Polyak tail-averaging for robust online parameter estimation.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • lam (float or None)

  • lam_scale (float)

iterate(A, b, n_iters=None, x0=None, tol=0.0, rng=None, burnin=0)[source]#

Run TAG-K: greedy Kaczmarz + Tikhonov + tail-averaging.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • n_iters (int or None)

  • x0 (np.ndarray or None)

  • tol (float)

  • rng (np.random.Generator or None)

  • burnin (int)

Returns:

Tail-averaged iterate.

Return type:

np.ndarray, shape (n,)

Block Methods#

Block and specialised Kaczmarz variants.

  • FDBK – Fast Deterministic Block Kaczmarz

  • IGRK – Improved Greedy Randomized Kaczmarz

  • MGRK – Momentum-accelerated Greedy RK

  • REK – Randomized Extended Kaczmarz (handles inconsistent systems)

class online_estimators.estimators.block.FDBK(num_params, x0=None)[source]#

Bases: BaseEstimator

Fast Deterministic Block Kaczmarz (FDBK).

At each iteration, constructs a block of greedy rows (those with large per-row residuals) and performs a single combined projection. This can converge faster than single-row methods on well-structured systems.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

References

Necoara, I. “Faster randomized block Kaczmarz algorithms.” SIAM J. Matrix Anal. Appl., 40(4), 2019.

iterate(A, b, tol=0.0001, eps_row=1e-12)[source]#

Run one pass of Fast Deterministic Block Kaczmarz.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • tol (float) – Convergence tolerance on ||r||^2.

  • eps_row (float) – Numerical floor.

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.block.IGRK(num_params, x0=None)[source]#

Bases: BaseEstimator

Improved Greedy Randomized Kaczmarz.

Uses a stricter greedy threshold (based on crit-max + Frobenius contribution) and runs m*n inner iterations per call.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

iterate(A, b, eps=1e-12)[source]#

Run m*n IGRK sweeps.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.block.MGRK(num_params, x0=None, alpha=1.0, beta=0.25, theta=0.5)[source]#

Bases: BaseEstimator

Momentum-accelerated Greedy Randomized Kaczmarz.

Adds a heavy-ball momentum term beta(x_k - x_{k-1}) to the standard Kaczmarz update for faster convergence on ill-conditioned systems.

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

  • alpha (float) – Step size multiplier (default 1.0).

  • beta (float) – Momentum coefficient (default 0.25).

  • theta (float) – Threshold blending parameter (default 0.5).

iterate(A, b, eps=1e-12)[source]#

Run m*n momentum-accelerated greedy iterations.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float)

Return type:

np.ndarray, shape (n,)

class online_estimators.estimators.block.REK(num_params, x0=None)[source]#

Bases: BaseEstimator

Randomized Extended Kaczmarz.

Simultaneously projects onto both row and column spaces of A, allowing convergence even for inconsistent systems (where b not in range(A)).

Parameters:

  • num_params (int)

  • x0 (np.ndarray or None)

References

Zouzias, A. & Freris, N. “Randomized extended Kaczmarz for solving least squares.” SIAM J. Matrix Anal. Appl., 34(2), 2013.

iterate(A, b, eps=1e-06, max_passes=2)[source]#

Run REK until convergence or max_passes epochs.

Parameters:

  • A (np.ndarray, shape (m, n))

  • b (np.ndarray, shape (m,))

  • eps (float) – Convergence tolerance (primal + dual).

  • max_passes (int) – Maximum number of passes over the rows.

Return type:

np.ndarray, shape (n,)

C++ Backend Loader#

Optional C++ backend for estimators.

If the online_estimation C++ extension is installed, estimator classes will delegate to compiled implementations for better performance. The extension is built from the cpp/ directory via pip install ./cpp.

When the extension is not available, all estimators fall back to their pure-Python implementations transparently.