linfa_reduction/random_projection/
common.rs

1/// Compute a safe dimension for a projection with precision `eps`,
2/// using the Johnson-Lindestrauss Lemma.
3///
4/// References:
5/// - [D. Achlioptas, JCSS](https://www.sciencedirect.com/science/article/pii/S0022000003000254)
6/// - [Li et al., SIGKDD'06](https://hastie.su.domains/Papers/Ping/KDD06_rp.pdf)
7pub(crate) fn johnson_lindenstrauss_min_dim(n_samples: usize, eps: f64) -> usize {
8    let log_samples = (n_samples as f64).ln();
9    let value = 4. * log_samples / (eps.powi(2) / 2. - eps.powi(3) / 3.);
10    value as usize
11}
12
13#[cfg(test)]
14mod tests {
15    use super::*;
16
17    #[test]
18    /// Test against values computed by the scikit-learn implementation
19    /// of `johnson_lindenstrauss_min_dim`.
20    fn test_johnson_lindenstrauss() {
21        assert_eq!(johnson_lindenstrauss_min_dim(100, 0.05), 15244);
22        assert_eq!(johnson_lindenstrauss_min_dim(100, 0.1), 3947);
23        assert_eq!(johnson_lindenstrauss_min_dim(100, 0.2), 1062);
24        assert_eq!(johnson_lindenstrauss_min_dim(100, 0.5), 221);
25        assert_eq!(johnson_lindenstrauss_min_dim(1000, 0.05), 22867);
26        assert_eq!(johnson_lindenstrauss_min_dim(1000, 0.1), 5920);
27        assert_eq!(johnson_lindenstrauss_min_dim(1000, 0.2), 1594);
28        assert_eq!(johnson_lindenstrauss_min_dim(1000, 0.5), 331);
29        assert_eq!(johnson_lindenstrauss_min_dim(5000, 0.05), 28194);
30        assert_eq!(johnson_lindenstrauss_min_dim(5000, 0.1), 7300);
31        assert_eq!(johnson_lindenstrauss_min_dim(5000, 0.2), 1965);
32        assert_eq!(johnson_lindenstrauss_min_dim(5000, 0.5), 408);
33        assert_eq!(johnson_lindenstrauss_min_dim(10000, 0.05), 30489);
34        assert_eq!(johnson_lindenstrauss_min_dim(10000, 0.1), 7894);
35        assert_eq!(johnson_lindenstrauss_min_dim(10000, 0.2), 2125);
36        assert_eq!(johnson_lindenstrauss_min_dim(10000, 0.5), 442);
37    }
38}
linfa_reduction/random_projection/common.rs

linfa_reduction/random_projection/
common.rs
