1use 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#[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
31pub 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 r = svd.V() * svd.U().transpose();
72 }
73
74 Ok(mat_to_row_major(r.as_ref()))
75}
76
77pub 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 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 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 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}