//! PCA over a correlation matrix. //! //! The correlation matrix is *the* input: PCA of standardised traits is the //! eigendecomposition of R, so this needs no second data path and no refetch -- //! which is also why it waits for the matrix to be trustworthy (ai-memory #106: //! the r matrix first, PCA behind its own parity test). //! //! Two decisions that a reader will want, both taken from #103: //! //! * **Traits with a gap are dropped, and named.** A correlation matrix from //! real data has cells that are null (overlap below `min_overlap`), and a //! component computed from a matrix with holes is not defined. GN2 silently //! mutates its shared-sample list to force a rectangle; that produces a //! component nobody can reproduce. Here every dropped trait travels in //! `dropped`, so a caller can see why their favourite trait is missing. //! * **The sign convention is fixed**: within a component, the loading with the //! largest absolute value is made positive. Eigenvectors are defined up to //! sign, so without a rule two correct implementations disagree, and a parity //! test could never be exact. //! //! The decomposition itself is the cyclic Jacobi method -- symmetric, small //! matrices, no LAPACK and no new dependency. It is the slow way to do it //! (O(n^3) per sweep) and that is why `MAX_PCA_TRAITS` exists: this is for the //! tens-to-hundreds of traits a collection holds, not for a whole dataset. use crate::routes::correlation_matrix::Matrix; /// Most traits a PCA will fold in. Jacobi is O(n^3) per sweep with several /// sweeps, so 300 traits is already ~10^8 operations; a collection is a few /// hundred traits at most, and a dataset is not what this is for. pub const MAX_PCA_TRAITS: usize = 300; /// One principal component. #[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] pub struct Component { /// Eigenvalue of the correlation matrix (its variance, since the traits are /// standardised). pub eigenvalue: f64, /// `eigenvalue / number of traits`: the share of total variance. pub explained_variance_ratio: f64, /// Loading of each kept trait, in the reply's trait order, sign-fixed. pub loadings: Vec, } /// The eigendecomposition, plus what it had to leave out. #[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] pub struct Pca { /// Components, largest eigenvalue first. pub components: Vec, /// Eigenvalues in the same order, so a scree plot does not have to dig. pub scree: Vec, /// `{dataset, trait_name}` of every trait the PCA could not use, with the /// reason. pub dropped: Vec, /// Eigenvalues should sum to the number of traits; reported so a caller can /// check that the decomposition is sane rather than trust it. pub trace: f64, } #[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] pub struct Dropped { pub dataset: String, pub trait_name: String, pub reason: String, } /// Eigenvalues (descending) and eigenvectors (columns) of a symmetric matrix. /// /// Returns `None` when the matrix is not square, not symmetric within a /// tolerance, or larger than [`MAX_PCA_TRAITS`]. pub fn symmetric_eigen(matrix: &[Vec]) -> Option<(Vec, Vec>)> { let n = matrix.len(); if n == 0 || n > MAX_PCA_TRAITS || matrix.iter().any(|row| row.len() != n) { return None; } // Symmetry is a precondition, not a nicety: Jacobi silently produces // garbage for a matrix that only looks symmetric. for i in 0..n { for j in 0..i { let scale = matrix[i][j].abs().max(matrix[j][i].abs()).max(1.0); if (matrix[i][j] - matrix[j][i]).abs() > 1e-12 * scale { return None; } } } let mut a = matrix.to_vec(); let mut v = vec![vec![0.0; n]; n]; for (i, row) in v.iter_mut().enumerate() { row[i] = 1.0; } for _sweep in 0..100 { let mut off_diagonal = 0.0; for i in 0..n { for j in (i + 1)..n { off_diagonal += a[i][j] * a[i][j]; } } if off_diagonal.sqrt() < 1e-14 { break; } for p in 0..n { for q in (p + 1)..n { if a[p][q].abs() < 1e-300 { continue; } // Jacobi rotation that zeroes a[p][q]. let theta = (a[q][q] - a[p][p]) / (2.0 * a[p][q]); let t = theta.signum() / (theta.abs() + (theta * theta + 1.0).sqrt()); let c = 1.0 / (t * t + 1.0).sqrt(); let s = t * c; for k in 0..n { let akp = a[k][p]; let akq = a[k][q]; a[k][p] = c * akp - s * akq; a[k][q] = s * akp + c * akq; } for k in 0..n { let apk = a[p][k]; let aqk = a[q][k]; a[p][k] = c * apk - s * aqk; a[q][k] = s * apk + c * aqk; } for k in 0..n { let vkp = v[k][p]; let vkq = v[k][q]; v[k][p] = c * vkp - s * vkq; v[k][q] = s * vkp + c * vkq; } } } } let mut order: Vec = (0..n).collect(); order.sort_by(|x, y| a[*y][*y].partial_cmp(&a[*x][*x]).unwrap_or(std::cmp::Ordering::Equal)); let eigenvalues: Vec = order.iter().map(|i| a[*i][*i]).collect(); let mut eigenvectors = vec![vec![0.0; n]; n]; for (column, source) in order.iter().enumerate() { // Sign convention: largest absolute loading positive. let mut largest = 0usize; for row in 0..n { if v[row][*source].abs() > v[largest][*source].abs() { largest = row; } } let flip = if v[largest][*source] < 0.0 { -1.0 } else { 1.0 }; for row in 0..n { eigenvectors[row][column] = flip * v[row][*source]; } } Some((eigenvalues, eigenvectors)) } /// PCA of a correlation matrix, dropping the traits the matrix cannot place. pub fn analyse(matrix: &Matrix) -> Pca { let size = matrix.r.len(); let mut dropped: Vec = Vec::new(); let mut kept: Vec = Vec::new(); for (index, trait_ref) in matrix.traits.iter().enumerate() { let mut reason = None; if index >= size { reason = Some("the matrix has no row for this trait".to_string()); } else { for (other, cell) in matrix.r[index].iter().enumerate() { if cell.is_none() { reason = Some(format!( "no correlation with trait {}, so the matrix has a gap", other + 1 )); break; } } } match reason { Some(reason) => dropped.push(Dropped { dataset: trait_ref.dataset.clone(), trait_name: trait_ref.trait_name.clone(), reason, }), None => kept.push(index), } } let n = kept.len(); if n < 2 || n > MAX_PCA_TRAITS { return Pca { components: Vec::new(), scree: Vec::new(), dropped, trace: 0.0, }; } let small: Vec> = kept .iter() .map(|row| kept.iter().map(|column| matrix.r[*row][*column].unwrap_or(0.0)).collect()) .collect(); let Some((eigenvalues, eigenvectors)) = symmetric_eigen(&small) else { return Pca { components: Vec::new(), scree: Vec::new(), dropped, trace: 0.0, }; }; let trace: f64 = eigenvalues.iter().sum(); let components = eigenvalues .iter() .enumerate() .map(|(column, eigenvalue)| Component { eigenvalue: *eigenvalue, // Traits are standardised, so the total variance is the number of // traits and the trace should equal it; the ratio divides by n, not // by the trace, so rounding in the trace cannot skew it. explained_variance_ratio: eigenvalue / n as f64, loadings: (0..n).map(|row| eigenvectors[row][column]).collect(), }) .collect(); Pca { components, scree: eigenvalues, dropped, trace, } } #[cfg(test)] mod tests { use super::*; fn assert_close(a: f64, b: f64, tolerance: f64) { assert!((a - b).abs() < tolerance, "{a} vs {b}"); } #[test] fn identity_has_unit_eigenvalues() { let (values, vectors) = symmetric_eigen(&[vec![1.0, 0.0, 0.0], vec![0.0, 1.0, 0.0], vec![0.0, 0.0, 1.0]]) .expect("identity"); assert_eq!(values.len(), 3); for value in &values { assert_close(*value, 1.0, 1e-12); } // Orthonormal columns. for column in 0..3 { let norm: f64 = (0..3).map(|row| vectors[row][column].powi(2)).sum(); assert_close(norm, 1.0, 1e-12); } } #[test] fn a_known_two_by_two_splits_into_1_plus_minus_rho() { // Eigenvalues of [[1, r], [r, 1]] are 1+r and 1-r. let rho = 0.5; let (values, vectors) = symmetric_eigen(&[vec![1.0, rho], vec![rho, 1.0]]).expect("2x2"); assert_eq!(values.len(), 2); assert_close(values[0], 1.5, 1e-12); assert_close(values[1], 0.5, 1e-12); // Sign convention: the largest absolute loading is positive. assert!(vectors[0][0] > 0.0 && vectors[1][0] > 0.0); } #[test] fn the_trace_is_the_number_of_traits() { let rho = -0.3; let matrix = vec![ vec![1.0, rho, 0.2], vec![rho, 1.0, 0.1], vec![0.2, 0.1, 1.0], ]; let (values, _) = symmetric_eigen(&matrix).expect("3x3"); let trace: f64 = values.iter().sum(); assert_close(trace, 3.0, 1e-12); // Descending. assert!(values[0] >= values[1] && values[1] >= values[2]); } #[test] fn a_non_symmetric_matrix_is_refused() { assert!(symmetric_eigen(&[vec![1.0, 0.5], vec![0.4, 1.0]]).is_none()); } #[test] fn the_too_large_case_is_refused() { let big = vec![vec![1.0; MAX_PCA_TRAITS + 1]; MAX_PCA_TRAITS + 1]; assert!(symmetric_eigen(&big).is_none()); } }