sketch_freq_directions.nx

sketch_freq_directions.nx -- Liberty 2013 Frequent Directions sketch. Streaming low-rank matrix approximation. Given a stream of input rows in R^d, maintain a sketch matrix B in R^(l x d) (l << n) such that B^T B approximates A^T A to within an additive error bound based on the tail singular values: || A^T A - B^T B ||_F <= || A - A_k ||_F^2 / (l - k) where A_k is the best rank-k approximation of A. Direct matrix-valued analog of Misra-Gries frequency counting (Liberty's own framing in the 2013 STOC paper). ALGORITHM: For each input row x in R^d: 1. If any row of B is "empty" (all zeros) -> copy x into it. 2. Else -> shrink: a. Compute SVD: B = U Σ V^T b. delta := σ_l^2 (smallest singular value squared) c. Shrunk singular values: σ_i'^2 := max(0, σ_i^2 - delta) d. B := diag(sqrt(σ_i'^2)) V^T -- by construction the last row has σ_l' = 0 (empty) e. Copy x into the now-empty row. SVD WITHOUT f64 (the technical chokepoint -- see queued roadmap 2026-05-10): This reference impl uses POWER ITERATION with DEFLATION in Q14 fixed-point. Bounded to l <= 4, d <= 8 for this version -- convergence guarantee at small sizes is reliable; for larger matrices the accumulated round-off in Q14 degrades the shrink quality. v2 will swap in fixed-point Jacobi or bidiagonal + QR for arbitrary size. MATURITY = REFERENCE_IMPL with EXPLICIT size limits. Substrate callers requesting larger l or d get NX_FD_ERR_TOO_BIG at alloc. COMPOSITION: - Complements sketch_kmeans1d (clustering family) for streaming dimensionality reduction before clustering. - Complements sketch_correlation for streaming low-rank