#8 Cannot build rust crate for `no_std`

[Adrian Figueroa]

Hello!

Firstly, thanks for providing this library! I intend to use it on an embedded platform and am trying to build your crate in a no_std environment, which should work, but doesn't.

The nalgebra dependency pulls in std, because it is not included with default-features = false, so the build fails.

Best regards

[Adrian Figueroa]

This builds fine in a no_std environment.

[package]
name = "bayes_estimate"
version = "0.17.0"
authors = ["Michael Stevens <mail@michael-stevens.de>"]
edition = "2024"
description = "Bayesian estimation library. Kalman filter, Informatiom, Square root, Information root, Unscented and UD filters. Numerically and dimensionally generic implementation using nalgebra. Provides fast numerically stable estimation solutions."
repository = "https://sourceforge.net/p/bayesclasses/rustcode"
readme = "README.md"
categories = ["science", "science::robotics"]
keywords = ["kalman", "bayesian", "linear", "discrete", 'no_std']
license = "MIT"


[dependencies]
nalgebra = { version = "0.33", default-features = false }
rand_core = { version = "0.9", default-features = false }
rand_distr = { version = "0.5", default-features = false }
num-traits = { version = "0.2", default-features = false }

[dev-dependencies]
approx = "0.5"
rand = "0.9"

[lib]
name = "bayes_estimate"
path = "src/lib.rs"

[features]
default = ["std"]
std = ["nalgebra/std", "rand_core/std", "rand_distr/std", "num-traits/std"]

I also noticed a build warning

warning: function `quadform_tr_x` is never used
  --> /home/adf/repo/mars/rust/bayes-estimate/src/matrix/mat.rs:34:8
   |
34 | pub fn quadform_tr_x<N: Copy + RealField, D1, S, R3, C3, S3>(
   |        ^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

It would need to be gated behind the std feature as well

/// Computes the quadratic form `mat = alpha * lhs * lhs.transpose() + beta * mat`.
///
/// there is no 'mid'.
#[cfg(feature = "std")]
pub fn quadform_tr_x<N: Copy + RealField, D1, S, R3, C3, S3>(
    mat: &mut SquareMatrix<N, D1, S>,
    alpha: N,
// ...

[Michael Stevens]

I've tried this out. Problem is that the tests require std from nalgebra

To make that work I need:

[dev-dependencies]
nalgebra = { version = "0.33", default-features = true }

Seems rather clumsy! As the version has to be specified again. Any ideas how to do this better?

[Adrian Figueroa]

Unfortunately not. I think there is no official way to solve this problem: https://github.com/rust-lang/cargo/issues/2911

[Adrian Figueroa]

By extension, I wanted to use the unscented_duplex module, so I made it rely on alloc instead of std. Here is the full diff. Sorry for the formatting noise, this is from cargo fmt.

diff --git a/Cargo.toml b/Cargo.toml
index aa7903a..3ddff25 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -6,18 +6,19 @@ edition = "2024"
 description = "Bayesian estimation library. Kalman filter, Informatiom, Square root, Information root, Unscented and UD filters. Numerically and dimensionally generic implementation using nalgebra. Provides fast numerically stable estimation solutions."
 repository = "https://sourceforge.net/p/bayesclasses/rustcode"
 readme = "README.md"
-categories = [ "science", "science::robotics" ]
-keywords = [ "kalman", "bayesian", "linear", "discrete", 'no_std' ]
+categories = ["science", "science::robotics"]
+keywords = ["kalman", "bayesian", "linear", "discrete", 'no_std']
 license = "MIT"


 [dependencies]
-nalgebra = {version = "0.33"}
-rand_core = "0.9"
-rand_distr = "0.5"
-num-traits = "0.2"
+nalgebra = { version = "0.33", default-features = false }
+rand_core = { version = "0.9", default-features = false }
+rand_distr = { version = "0.5", default-features = false }
+num-traits = { version = "0.2", default-features = false }

 [dev-dependencies]
+nalgebra = "0.33"
 approx = "0.5"
 rand = "0.9"

@@ -27,4 +28,5 @@ path = "src/lib.rs"

 [features]
 default = ["std"]
-std = []
+alloc = []
+std = ["nalgebra/std", "rand_core/std", "rand_distr/std", "num-traits/std"]
diff --git a/src/estimators/mod.rs b/src/estimators/mod.rs
index 87f0049..1a87c16 100644
--- a/src/estimators/mod.rs
+++ b/src/estimators/mod.rs
@@ -6,5 +6,5 @@ pub mod information_root;
 #[cfg(feature = "std")]
 pub mod sir;
 pub mod ud;
-#[cfg(feature = "std")]
+#[cfg(feature = "alloc")]
 pub mod unscented_duplex;
diff --git a/src/estimators/unscented_duplex.rs b/src/estimators/unscented_duplex.rs
index 68ef516..d98af3b 100644
--- a/src/estimators/unscented_duplex.rs
+++ b/src/estimators/unscented_duplex.rs
@@ -8,7 +8,10 @@
 //! The transform evaluates the non-linear predict and observe functions at duplex 'sigma' points about the mean to provide an
 //! estimate of the distribution. The transforms can be optimised for particular functions by vary the Kappa parameter from its usual value of 1.

-use nalgebra::{allocator::Allocator, DefaultAllocator, Dim, OMatrix, OVector, RealField, U1};
+#[cfg(not(feature = "std"))]
+use alloc::vec::Vec;
+
+use nalgebra::{DefaultAllocator, Dim, OMatrix, OVector, RealField, U1, allocator::Allocator};

 use crate::linalg::rcond;
 use crate::matrix::quadform_tr_x;
@@ -28,8 +31,8 @@ where
 }

 impl<N: RealField, D: Dim> UnscentedDuplexState<N, D>
-    where
-        DefaultAllocator: Allocator<D, D> + Allocator<D>,
+where
+    DefaultAllocator: Allocator<D, D> + Allocator<D>,
 {
     // Construct with KalmanState and standard optimal 'kappa' value.
     pub fn new_standard_kappa(state: KalmanState<N, D>) -> UnscentedDuplexState<N, D> {
@@ -38,8 +41,7 @@ impl<N: RealField, D: Dim> UnscentedDuplexState<N, D>
     }
 }

-impl<N: Copy + FromPrimitive + RealField, D: Dim> FunctionalPredictor<N, D>
-    for UnscentedDuplexState<N, D>
+impl<N: Copy + FromPrimitive + RealField, D: Dim> FunctionalPredictor<N, D> for UnscentedDuplexState<N, D>
 where
     DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
 {
@@ -68,8 +70,7 @@ where
     }
 }

-impl<N: Copy + FromPrimitive + RealField, D: Dim, ZD: Dim> FunctionalObserver<N, D, ZD>
-    for UnscentedDuplexState<N, D>
+impl<N: Copy + FromPrimitive + RealField, D: Dim, ZD: Dim> FunctionalObserver<N, D, ZD> for UnscentedDuplexState<N, D>
 where
     DefaultAllocator: Allocator<D, D>
         + Allocator<D>
@@ -135,10 +136,9 @@ where
     }
 }

-impl<N: Copy + FromPrimitive + RealField, D: Dim> Estimator<N, D>
-for UnscentedDuplexState<N, D>
-    where
-        DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
+impl<N: Copy + FromPrimitive + RealField, D: Dim> Estimator<N, D> for UnscentedDuplexState<N, D>
+where
+    DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
 {
     fn state<'e>(&self) -> Result<OVector<N, D>, &'e str> {
         Ok(self.kalman.x.clone())
@@ -146,16 +146,15 @@ for UnscentedDuplexState<N, D>
 }

 impl<N: Copy + FromPrimitive + RealField, D: Dim> From<KalmanState<N, D>> for UnscentedDuplexState<N, D>
-    where
-        DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
+where
+    DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
 {
     fn from(state: KalmanState<N, D>) -> Self {
         UnscentedDuplexState::new_standard_kappa(state)
     }
 }

-impl<N: Copy + FromPrimitive + RealField, D: Dim> KalmanEstimator<N, D>
-    for UnscentedDuplexState<N, D>
+impl<N: Copy + FromPrimitive + RealField, D: Dim> KalmanEstimator<N, D> for UnscentedDuplexState<N, D>
 where
     DefaultAllocator: Allocator<D, D> + Allocator<D> + Allocator<U1, D>,
 {
@@ -203,13 +202,7 @@ where
     where
         DefaultAllocator: Allocator<D, D> + Allocator<D>,
     {
-        let sigma = self
-            .X
-            .clone()
-            .cholesky()
-            .ok_or("to_unscented_duplex, X not PSD")?
-            .l()
-            * scale.sqrt();
+        let sigma = self.X.clone().cholesky().ok_or("to_unscented_duplex, X not PSD")?.l() * scale.sqrt();

         // Generate UU with the same sample Mean and Covariance
         let mut UU: Vec<OVector<N, D>> = Vec::with_capacity(2 * self.x.nrows() + 1);
diff --git a/src/lib.rs b/src/lib.rs
index 4cc1074..35a16a2 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -19,12 +19,14 @@

 #![cfg_attr(not(feature = "std"), no_std)]

+#[cfg(feature = "alloc")]
+extern crate alloc;
 extern crate core;

 /// Library represents models, noise and estimators.
+pub mod estimators;
 pub mod models;
 pub mod noise;
-pub mod estimators;

 mod linalg;
 mod matrix;

[Michael Stevens]

Thanks for the feedback. I think unscented_duplex should not really use Vec. Better would be to use a nalgebra Matrix which doesn't need alloc if a fixed size is used.

[Michael Stevens]

Please note my unscented_duplex is based on the original paper by Julier and Uhlmann. There are more recent variant which chose the sigma points differently which may be better.

[Adrian Figueroa]

I see. We had previously used Van der Merwe's method. I will try to contribute such a sigma point generation, as it seems like it would be easily doable.

I think unscented_duplex should not really use Vec

Yes, but I don't think there is a better choice at the moment. As far as I know, rust doesn't yet support calculations with const generics, such as [2 * N + 1] for array sizes, where N is a const generic usize. If a user knew how to calculate the required generic size, then that length could be passed directly, but I don't find that very user friendly.

Otherwise, this problem could be fixed using a heapless::Vec with some upper limit in length. For now, alloc::Vec is probably the safest choice.

[Michael Stevens]

Hi Adrian,

I had a look last week into using a nalgebra::Matrix for the Sigma point. I now know why I originally chose to use a std::Vec of nalgebra::Matrix to do this! I think in principle it is possible using the DimSum (with DimAdd) as type constraint. But the whole type signature becomes totally unwieldy. I will scrub that idea and use alloc::Vec so it is buildable with 'no_std'.

[Michael Stevens]

Hi Adrain,

The implementation you used follows that in the paper
https://groups.seas.harvard.edu/courses/cs281/papers/unscented.pdf ?

It would be good if we could get that or similar into the library.

Michael

[Michael Stevens]

I've pushed version 0.18.1. Since I was only using Vec from std I have changed the library to be completely 'no_std'. There is no 'std' feature anymore making things much simpler.

I have removed the old 'unscented_duplex' and replaced it with 'unscented'. This has a more modern parameterisation of the 'sigma' point weights.

I've implemented 'unscented_root'. I have marked it as experimental.

[Adrian Figueroa]

Great, thanks for your efforts!

I wonder, what method is now used for sigma point generation? Is it still the same? The module docstring appears to be out of data, since it still mentions kappa, although it doesn't exist as a parameter anymore.

Looks like you moved to Van der Merwe's method already, correct? So kappa is always zero if I read your equations correctly.

[Michael Stevens]

Opps, the module docstring was not updated. Sigma point parametrisation are identical to the SRUF in Van der Merwe paper. Effectively kappa is replaced by alpha and beta.
I have pushed a corrected docstring in "main", thanks.

There are various preprint and papers from Simon Julier titled "The scaled unscented transform" that introduce and analyse the alpha and beta parametrisation for choosing sigma points.

[Adrian Figueroa]

Thanks! We now get vastly different/incorrect output in the observe step of the unscented estimator using alpha = 0.1 and beta = 2.0 as opposed to the old implementation. Is there something else to be aware of?

[Michael Stevens]

Annoying. The new implementation should follow that in the Merwe and Wan paper. I test with alpha =1 which is at the opposite extreme from alpha = 0.1. In the paper there mention alpha = 0.001 Looks like I need to do more testing. The only other implementation I found is in Python again changes the parametersation and reintroduces a kappa. I can find no publication mention or any mathematical justification so I have avoided that.

Maybe just copy the old unscented_duplex from older releases back into the source code. Should work fine if you 'use alloc::vec::Vec;'. If you need a crates release with it back in I can do that.

Michael

[Adrian Figueroa]

Yes, I can use a fork that I modified already, no problem.

Can I somehow help with testing the unscented approach? By the way, the output of the predict step didn't change much with the new implementation, only observe.

[Michael Stevens]

I've retested. 'simple_unscented' with alpha 1e-3 give identical results as alpha 1, which is to be expected as the 'simple' test is linear. 'rtheta_unscented' with alpha 1e-3 changes a little but looks reasonable.

Since you are only having a problem in observe I wonder if the problem is related to the size of the observation vector. The test I have it only a two dimensional observation. What are the dimensions of your models. Is the observation function discontinues?

[Michael Stevens]

Interestingly the earlier Wan & Merwe paper 'The Unscented KalmanFilter for Nonlinear Estimation' has a 'kappa' in the formulation of weights. It has a completely different definition to that in the original Julier & Uhlman paper. They simply state 'kappa is a secondary scaling parameter which is usually set to 0'!