1use faer::{Mat, MatRef};
4use rand::SeedableRng;
5use rand_chacha::ChaCha8Rng;
6use rand_distr::{Distribution, StandardNormal};
7
8use crate::error::{LittleBitError, Result};
9
10pub const DEFAULT_LOWRANK_NITER: usize = 2;
12
13#[derive(Debug, Clone, PartialEq)]
15pub struct ThinSvd {
16 pub u: Vec<f32>,
18 pub s: Vec<f32>,
20 pub vt: Vec<f32>,
22 pub rows: usize,
24 pub cols: usize,
26 pub rank: usize,
28}
29
30#[inline]
31pub(crate) fn mat_from_row_major(data: &[f32], rows: usize, cols: usize) -> Result<Mat<f32>> {
32 if data.len() != rows.saturating_mul(cols) {
33 return Err(LittleBitError::InvalidShape {
34 expected: format!("{rows}x{cols} ({} elements)", rows * cols),
35 actual: format!("{} elements", data.len()),
36 });
37 }
38 Ok(Mat::from_fn(rows, cols, |r, c| data[r * cols + c]))
39}
40
41#[inline]
42pub(crate) fn mat_to_row_major(mat: MatRef<'_, f32>) -> Vec<f32> {
43 let (rows, cols) = (mat.nrows(), mat.ncols());
44 let mut out = Vec::with_capacity(rows * cols);
45 for r in 0..rows {
46 for c in 0..cols {
47 out.push(mat[(r, c)]);
48 }
49 }
50 out
51}
52
53pub fn exact_thin_svd(data: &[f32], rows: usize, cols: usize) -> Result<ThinSvd> {
59 if rows == 0 || cols == 0 {
60 return Err(LittleBitError::InvalidShape {
61 expected: "non-empty matrix".to_string(),
62 actual: format!("{rows}x{cols}"),
63 });
64 }
65 let mat = mat_from_row_major(data, rows, cols)?;
66 let svd = mat
67 .thin_svd()
68 .map_err(|err| LittleBitError::SvdFailed(format!("{err:?}")))?;
69
70 let rank = rows.min(cols);
71 let u_ref = svd.U();
72 let v_ref = svd.V();
73 let s_ref = svd.S().column_vector();
74
75 let mut u = Vec::with_capacity(rows * rank);
76 for r in 0..rows {
77 for k in 0..rank {
78 u.push(u_ref[(r, k)]);
79 }
80 }
81
82 let mut s = Vec::with_capacity(rank);
83 for k in 0..rank {
84 s.push(s_ref[k]);
85 }
86
87 let mut vt = Vec::with_capacity(rank * cols);
88 for k in 0..rank {
89 for c in 0..cols {
90 vt.push(v_ref[(c, k)]);
91 }
92 }
93
94 Ok(ThinSvd {
95 u,
96 s,
97 vt,
98 rows,
99 cols,
100 rank,
101 })
102}
103
104pub fn svd_lowrank(
112 data: &[f32],
113 rows: usize,
114 cols: usize,
115 rank: usize,
116 niter: usize,
117 seed: u64,
118) -> Result<ThinSvd> {
119 if rows == 0 || cols == 0 || rank == 0 {
120 return Err(LittleBitError::InvalidShape {
121 expected: "non-zero rows, cols, and rank".to_string(),
122 actual: format!("rows={rows}, cols={cols}, rank={rank}"),
123 });
124 }
125
126 let min_dim = rows.min(cols);
127 let target_rank = rank.min(min_dim);
128
129 if min_dim <= 256 || target_rank + 10 >= min_dim {
130 let exact = exact_thin_svd(data, rows, cols)?;
131 return Ok(truncate_svd(exact, target_rank));
132 }
133
134 let sketch_dim = (target_rank + 10).min(min_dim);
135 let mat = mat_from_row_major(data, rows, cols)?;
136
137 let mut rng = ChaCha8Rng::seed_from_u64(seed);
138 let omega = Mat::from_fn(cols, sketch_dim, |_, _| -> f32 {
139 StandardNormal.sample(&mut rng)
140 });
141
142 let mut y = &mat * ω
143 let mut q = y.qr().compute_thin_Q();
144
145 for _ in 0..niter {
146 let z = mat.transpose() * &q;
147 let qz = z.qr().compute_thin_Q();
148 y = &mat * &qz;
149 q = y.qr().compute_thin_Q();
150 }
151
152 let b = q.transpose() * &mat;
153 let b_svd = b
154 .thin_svd()
155 .map_err(|err| LittleBitError::SvdFailed(format!("{err:?}")))?;
156
157 let u_full = &q * b_svd.U();
158 let v_ref = b_svd.V();
159 let s_ref = b_svd.S().column_vector();
160
161 let mut u = Vec::with_capacity(rows * target_rank);
162 for r in 0..rows {
163 for k in 0..target_rank {
164 u.push(u_full[(r, k)]);
165 }
166 }
167
168 let mut s = Vec::with_capacity(target_rank);
169 for k in 0..target_rank {
170 s.push(s_ref[k]);
171 }
172
173 let mut vt = Vec::with_capacity(target_rank * cols);
174 for k in 0..target_rank {
175 for c in 0..cols {
176 vt.push(v_ref[(c, k)]);
177 }
178 }
179
180 Ok(ThinSvd {
181 u,
182 s,
183 vt,
184 rows,
185 cols,
186 rank: target_rank,
187 })
188}
189
190fn truncate_svd(svd: ThinSvd, target_rank: usize) -> ThinSvd {
191 if target_rank >= svd.rank {
192 return svd;
193 }
194 let mut u = Vec::with_capacity(svd.rows * target_rank);
195 for r in 0..svd.rows {
196 let row_start = r * svd.rank;
197 u.extend_from_slice(&svd.u[row_start..row_start + target_rank]);
198 }
199 let s = svd.s[..target_rank].to_vec();
200 let vt = svd.vt[..target_rank * svd.cols].to_vec();
201 ThinSvd {
202 u,
203 s,
204 vt,
205 rows: svd.rows,
206 cols: svd.cols,
207 rank: target_rank,
208 }
209}
210
211pub fn rank_one_decompose(
219 abs_data: &[f32],
220 rows: usize,
221 cols: usize,
222 seed: u64,
223) -> Result<(Vec<f32>, Vec<f32>)> {
224 let svd = svd_lowrank(abs_data, rows, cols, 1, 4, seed)?;
225 let sqrt_s0 = svd.s[0].max(0.0).sqrt();
226
227 let mut u_comp: Vec<f32> = (0..rows).map(|r| svd.u[r * svd.rank] * sqrt_s0).collect();
228 let mut v_comp: Vec<f32> = (0..cols).map(|c| svd.vt[c] * sqrt_s0).collect();
229
230 let u_sum: f32 = u_comp.iter().sum();
232 if u_sum < 0.0 {
233 for v in &mut u_comp {
234 *v = -*v;
235 }
236 for v in &mut v_comp {
237 *v = -*v;
238 }
239 }
240
241 Ok((u_comp, v_comp))
242}
243
244#[cfg(test)]
245mod tests {
246 use super::*;
247
248 #[test]
249 fn exact_thin_svd_reconstructs_rectangular_matrix() -> Result<()> {
250 let rows = 6;
251 let cols = 4;
252 let data: Vec<f32> = (0..rows * cols)
253 .map(|i| ((i * 7 + 2) % 13) as f32 * 0.25 - 1.1)
254 .collect();
255 let svd = exact_thin_svd(&data, rows, cols)?;
256 assert_eq!(svd.rank, 4);
257
258 for pair in svd.s.windows(2) {
260 assert!(pair[0] >= pair[1] && pair[1] >= 0.0);
261 }
262
263 let mut err_sq = 0.0f32;
265 for r in 0..rows {
266 for c in 0..cols {
267 let mut acc = 0.0f32;
268 for k in 0..svd.rank {
269 acc += svd.u[r * svd.rank + k] * svd.s[k] * svd.vt[k * cols + c];
270 }
271 let diff = data[r * cols + c] - acc;
272 err_sq += diff * diff;
273 }
274 }
275 assert!(err_sq.sqrt() < 1e-4, "reconstruction error: {err_sq}");
276 Ok(())
277 }
278
279 #[test]
280 fn randomized_lowrank_svd_recovers_low_rank_matrix() -> Result<()> {
281 let rows = 300;
282 let cols = 320;
283 let true_rank = 8;
284
285 let mut rng = ChaCha8Rng::seed_from_u64(123);
286 let a: Vec<f32> = (0..rows * true_rank)
287 .map(|_| StandardNormal.sample(&mut rng))
288 .collect();
289 let b: Vec<f32> = (0..true_rank * cols)
290 .map(|_| StandardNormal.sample(&mut rng))
291 .collect();
292
293 let mut mat = vec![0.0f32; rows * cols];
294 for r in 0..rows {
295 for c in 0..cols {
296 let mut acc = 0.0f32;
297 for k in 0..true_rank {
298 acc += a[r * true_rank + k] * b[k * cols + c];
299 }
300 mat[r * cols + c] = acc;
301 }
302 }
303
304 let svd = svd_lowrank(&mat, rows, cols, true_rank, 2, 42)?;
305 let mut norm_sq = 0.0f32;
306 let mut err_sq = 0.0f32;
307 for r in 0..rows {
308 for c in 0..cols {
309 let mut acc = 0.0f32;
310 for k in 0..true_rank {
311 acc += svd.u[r * true_rank + k] * svd.s[k] * svd.vt[k * cols + c];
312 }
313 let target = mat[r * cols + c];
314 norm_sq += target * target;
315 let diff = target - acc;
316 err_sq += diff * diff;
317 }
318 }
319 let rel_err = (err_sq / norm_sq).sqrt();
320 assert!(rel_err < 1e-4, "relative lowrank error too high: {rel_err}");
321 Ok(())
322 }
323
324 #[test]
325 fn rank_one_decompose_produces_non_negative_factors() -> Result<()> {
326 let data: Vec<f32> = (0..12).map(|i| (i + 1) as f32).collect();
327 let (u1, v1) = rank_one_decompose(&data, 3, 4, 7)?;
328 assert_eq!(u1.len(), 3);
329 assert_eq!(v1.len(), 4);
330 assert!(u1.iter().all(|&x| x >= 0.0));
331 assert!(v1.iter().all(|&x| x >= 0.0));
332 Ok(())
333 }
334}