Skip to main content

littlebit_core/
itq.rs

1//! LittleBit-2 Joint Iterative Quantization (Joint-ITQ) latent rotation.
2
3use faer::Mat;
4use rand::SeedableRng;
5use rand_chacha::ChaCha8Rng;
6use rand_distr::{Distribution, StandardNormal};
7
8use crate::error::{LittleBitError, Result};
9use crate::svd::{mat_from_row_major, mat_to_row_major};
10
11/// Generate a Haar-distributed orthogonal `(dim, dim)` matrix via QR with positive `R` diagonal.
12#[must_use]
13pub fn random_orthogonal_matrix(dim: usize, seed: u64) -> Mat<f32> {
14    let mut rng = ChaCha8Rng::seed_from_u64(seed);
15    let gaussian = Mat::from_fn(dim, dim, |_, _| -> f32 { StandardNormal.sample(&mut rng) });
16    let qr = gaussian.qr();
17    let mut q = qr.compute_thin_Q();
18    let r = qr.R();
19    for j in 0..dim {
20        let diag = r[(j, j)];
21        let sign = if diag < 0.0 { -1.0 } else { 1.0 };
22        if sign < 0.0 {
23            for i in 0..dim {
24                q[(i, j)] *= sign;
25            }
26        }
27    }
28    q
29}
30
31/// Find orthogonal rotation `R` of shape `(dim, dim)` aligning `X` (`(rows, dim)`)
32/// to the binary hypercube: `min_R || sign(X @ R) - X @ R ||_F^2`.
33///
34/// Exact Rust port of `LittleBitLinear._compute_itq_rotation`.
35///
36/// # Errors
37/// Returns an error if matrix dimensions are invalid or inner Procrustes SVD fails.
38pub fn compute_itq_rotation(
39    x_combined: &[f32],
40    rows: usize,
41    dim: usize,
42    n_iter: usize,
43    seed: u64,
44) -> Result<Vec<f32>> {
45    if rows == 0 || dim == 0 {
46        return Err(LittleBitError::InvalidShape {
47            expected: "non-empty matrix".to_string(),
48            actual: format!("{rows}x{dim}"),
49        });
50    }
51    let x = mat_from_row_major(x_combined, rows, dim)?;
52    let mut r = random_orthogonal_matrix(dim, seed);
53
54    for _ in 0..n_iter {
55        let z = &x * &r;
56        let b = Mat::from_fn(rows, dim, |i, j| {
57            let v = z[(i, j)];
58            if v > 0.0 {
59                1.0f32
60            } else if v < 0.0 {
61                -1.0f32
62            } else {
63                0.0f32
64            }
65        });
66        let m = b.transpose() * &x;
67        let svd = m
68            .thin_svd()
69            .map_err(|err| LittleBitError::SvdFailed(format!("ITQ SVD failed: {err:?}")))?;
70        // M = U_p * S * V_p^T => R = V_p * U_p^T (exact Procrustes solution).
71        r = svd.V() * svd.U().transpose();
72    }
73
74    Ok(mat_to_row_major(r.as_ref()))
75}
76
77/// Jointly align SVD factors `U` `(out_features, split_dim)` and `V` `(split_dim, in_features)`
78/// via `X_combined = [U; V^T]`, updating `U <- U @ R` and `V <- R^T @ V`.
79///
80/// # Errors
81/// Returns an error if factor slice sizes do not match dimensions or Joint-ITQ fails.
82pub fn apply_joint_itq(
83    u: &mut [f32],
84    v: &mut [f32],
85    out_features: usize,
86    in_features: usize,
87    split_dim: usize,
88    n_iter: usize,
89    seed: u64,
90) -> Result<()> {
91    if u.len() != out_features.saturating_mul(split_dim) {
92        return Err(LittleBitError::InvalidShape {
93            expected: format!("{out_features}x{split_dim}"),
94            actual: format!("{} elements", u.len()),
95        });
96    }
97    if v.len() != split_dim.saturating_mul(in_features) {
98        return Err(LittleBitError::InvalidShape {
99            expected: format!("{split_dim}x{in_features}"),
100            actual: format!("{} elements", v.len()),
101        });
102    }
103
104    let total_rows = out_features + in_features;
105    let mut x_combined = Vec::with_capacity(total_rows * split_dim);
106    x_combined.extend_from_slice(u);
107    for c in 0..in_features {
108        for r in 0..split_dim {
109            x_combined.push(v[r * in_features + c]);
110        }
111    }
112
113    let r_buf = compute_itq_rotation(&x_combined, total_rows, split_dim, n_iter, seed)?;
114    let r_mat = mat_from_row_major(&r_buf, split_dim, split_dim)?;
115
116    let u_mat = mat_from_row_major(u, out_features, split_dim)?;
117    let u_rot = &u_mat * &r_mat;
118    u.copy_from_slice(&mat_to_row_major(u_rot.as_ref()));
119
120    let v_mat = mat_from_row_major(v, split_dim, in_features)?;
121    let v_rot = r_mat.transpose() * &v_mat;
122    v.copy_from_slice(&mat_to_row_major(v_rot.as_ref()));
123
124    Ok(())
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    fn alignment_error(x: &[f32], r: &[f32], rows: usize, dim: usize) -> f32 {
132        let mut total = 0.0f32;
133        for i in 0..rows {
134            for j in 0..dim {
135                let mut z = 0.0f32;
136                for k in 0..dim {
137                    z += x[i * dim + k] * r[k * dim + j];
138                }
139                let b = if z >= 0.0 { 1.0 } else { -1.0 };
140                let d = b - z;
141                total += d * d;
142            }
143        }
144        total
145    }
146
147    #[test]
148    fn rotation_is_orthogonal_and_preserves_product() -> Result<()> {
149        let out_f = 24;
150        let in_f = 16;
151        let rank = 8;
152
153        let mut rng = ChaCha8Rng::seed_from_u64(99);
154        let u0: Vec<f32> = (0..out_f * rank)
155            .map(|_| StandardNormal.sample(&mut rng))
156            .collect();
157        let v0: Vec<f32> = (0..rank * in_f)
158            .map(|_| StandardNormal.sample(&mut rng))
159            .collect();
160
161        let r_buf = compute_itq_rotation(&u0, out_f, rank, 30, 5)?;
162        let r_mat = mat_from_row_major(&r_buf, rank, rank)?;
163        let rtr = r_mat.transpose() * &r_mat;
164        for i in 0..rank {
165            for j in 0..rank {
166                let want = if i == j { 1.0 } else { 0.0 };
167                assert!((rtr[(i, j)] - want).abs() < 1e-4, "R^T R[{i},{j}]");
168            }
169        }
170
171        let mut u = u0.clone();
172        let mut v = v0.clone();
173        apply_joint_itq(&mut u, &mut v, out_f, in_f, rank, 50, 11)?;
174
175        // Check U0 @ V0 == U @ V.
176        let u0_mat = mat_from_row_major(&u0, out_f, rank)?;
177        let v0_mat = mat_from_row_major(&v0, rank, in_f)?;
178        let prod0 = &u0_mat * &v0_mat;
179
180        let u_mat = mat_from_row_major(&u, out_f, rank)?;
181        let v_mat = mat_from_row_major(&v, rank, in_f)?;
182        let prod1 = &u_mat * &v_mat;
183
184        let mut max_diff = 0.0f32;
185        for i in 0..out_f {
186            for j in 0..in_f {
187                max_diff = max_diff.max((prod0[(i, j)] - prod1[(i, j)]).abs());
188            }
189        }
190        assert!(max_diff < 1e-4, "product drift: {max_diff}");
191        Ok(())
192    }
193
194    #[test]
195    fn joint_itq_improves_binary_hypercube_alignment() -> Result<()> {
196        let rows = 64;
197        let dim = 16;
198        let mut rng = ChaCha8Rng::seed_from_u64(42);
199        // Scale down lightly so binarization error responds to rotation.
200        let x: Vec<f32> = (0..rows * dim)
201            .map(|_| {
202                let s: f32 = StandardNormal.sample(&mut rng);
203                s * 0.5
204            })
205            .collect();
206        // Skewed columns concentrate energy on axis 0.
207        let mut skewed = x;
208        for i in 0..rows {
209            skewed[i * dim] *= 4.0;
210        }
211        let mut eye = vec![0.0f32; dim * dim];
212        for i in 0..dim {
213            eye[i * dim + i] = 1.0;
214        }
215        let before = alignment_error(&skewed, &eye, rows, dim);
216        let r = compute_itq_rotation(&skewed, rows, dim, 50, 7)?;
217        let after = alignment_error(&skewed, &r, rows, dim);
218        assert!(
219            after < before,
220            "ITQ should reduce hypercube alignment loss: before={before}, after={after}"
221        );
222        Ok(())
223    }
224}