Skip to main content

littlebit_core/
svd.rs

1//! Pure-Rust thin SVD and randomized low-rank SVD backed by `faer`.
2
3use faer::{Mat, MatRef};
4use rand::SeedableRng;
5use rand_chacha::ChaCha8Rng;
6use rand_distr::{Distribution, StandardNormal};
7
8use crate::error::{LittleBitError, Result};
9
10/// Default subspace iteration count matching `torch.svd_lowrank(..., niter=2)`.
11pub const DEFAULT_LOWRANK_NITER: usize = 2;
12
13/// Thin singular value decomposition `A ≈ U * diag(S) * V^T` stored row-major.
14#[derive(Debug, Clone, PartialEq)]
15pub struct ThinSvd {
16    /// Left singular vectors `(rows, rank)` in row-major order.
17    pub u: Vec<f32>,
18    /// Non-negative singular values `(rank,)` sorted in descending order.
19    pub s: Vec<f32>,
20    /// Right singular vectors transposed `(rank, cols)` in row-major order.
21    pub vt: Vec<f32>,
22    /// Number of rows in `A`.
23    pub rows: usize,
24    /// Number of columns in `A`.
25    pub cols: usize,
26    /// Retained rank `<= min(rows, cols)`.
27    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
53/// Compute exact thin SVD of a row-major `f32` matrix `(rows, cols)`.
54///
55/// # Errors
56/// Returns [`LittleBitError::InvalidShape`] on dimension mismatch or
57/// [`LittleBitError::SvdFailed`] if `faer` fails to converge.
58pub 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
104/// Compute a deterministic randomized low-rank SVD (`A ≈ U * diag(S) * V^T`),
105/// matching `torch.svd_lowrank` (Halko-Martinsson-Tropp Algorithm 5.1).
106///
107/// Falls back to exact thin SVD when `min(rows, cols) <= 256` or when `rank + 10 >= min(rows, cols)`.
108///
109/// # Errors
110/// Returns an error if the matrix is empty, dimensions mismatch `data.len()`, or SVD fails.
111pub 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 * &omega;
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
211/// Perform rank-1 SVD factorization on `abs_data` `(rows, cols)` returning `(u_scale, v_scale)`
212/// of lengths `rows` and `cols` such that `u_scale^T * v_scale ≈ abs_data`.
213///
214/// Matches `LittleBitLinear._rank_one_decompose`.
215///
216/// # Errors
217/// Returns an error if `abs_data` dimensions are invalid or SVD fails.
218pub 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    // Canonicalize Perron-Frobenius sign so non-negative matrices yield non-negative scales.
231    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        // Singular values are non-increasing and non-negative.
259        for pair in svd.s.windows(2) {
260            assert!(pair[0] >= pair[1] && pair[1] >= 0.0);
261        }
262
263        // Reconstruct U * diag(S) * Vt.
264        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}