code wiki / (root) / sketch_freq_directions_vs_topnorm_bench.nx

sketch_freq_directions_vs_topnorm_bench.nx

buildroot/runtime/sketch_freq_directions_vs_topnorm_bench.nx

6369 B223 linesdepth 5pulls 6 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_freq_directions_vs_topnorm_bench.nx -- paired bench, FD vs naive top-norm. CLAIM TO VALIDATE: Frequent Directions reconstructs the true covariance matrix A^T A more accurately than a naive "keep top-l rows by norm" baseline at the same sketch size. Liberty's headline 2013 theorem: ||A^T A - B^T B||_F <= ||A - A_k||_F^2 / (l - k). The naive baseline has no such guarantee -- it discards correlation information. SHARED WORKLOAD: - 50 random rows in d=4 dimensions, Q14 fixed-point in [0, 1) - Both sketches at l = 3 rows - Deterministic LCG generator seeded identically MEASUREMENT: true: G_true = A^T A (4x4 Gram matrix) FD est: G_fd = B_fd^T B_fd (4x4) naive est: G_naive = B_naive^T B_naive (where B_naive = top 3 rows of A by L2 norm) Scalar error metric (Frobenius): fd_err = sum_{i,j} (G_true[i,j] - G_fd[i,j])^2 naive_err = sum_{i,j} (G_true[i,j] - G_naive[i,j])^2 Smaller wins. Reuses nx_cmp_memory(our, theirs, tol) as the "scalar smaller-wins" comparator (the function does NOT care that the inputs are covariance-error rather than literal bytes; smaller-wins is the axis semantics). HARD-WIN GATE: verdict == BEATS with delta_ppm > 10000 (1% improvement).

dependencies 4 imports · 0 importers

syscalls.nx sketch_freq_directions.nx sketch_comparator.nx sketch_types.nx sketch_freq_directions_vs_topn

imports: syscalls.nxsketch_freq_directions.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_fd_alloc nx_fdb_outer_accumulate nx_fd_add_row nx_fd_empty_row_index nx_fd_row_norm_sq nx_fd_b_get nx_fd_shrink nx_fd_power_one nx_fd_deflate nx_fd_basis_get nx_fd_vnormalize nx_fd_vnorm_sq nx_fd_dot nx_fd_isqrt nx_fd_vscale nx_fd_matvec_Bv nx_fd_b_get ↻ nx_fd_matvec_Btw nx_fd_b_get ↻ nx_fd_vnorm_sq ↻ nx_fd_abs nx_fd_basis_set nx_fd_isqrt ↻ nx_fd_basis_get ↻ nx_fd_b_set nx_fd_row_norm_sq ↻ nx_fd_b_set ↻ nx_fdb_row_norm_sq nx_fd_b_get ↻ nx_fdb_frob_sq_diff nx_cmp_memory nx_fd_total_rows

structs

none

consts

40const NX_FDB_Q14: i64 = 16384
41const NX_FDB_D: i64 = 4
42const NX_FDB_L: i64 = 3
43const NX_FDB_N: i64 = 50
45const NX_FDB_LCG_A: i64 = 1103515245
46const NX_FDB_LCG_C: i64 = 12345
47const NX_FDB_LCG_MOD: i64 = 0x7FFFFFFF

functions

49func nx_fdb_row_norm_sq(row: *i64, d: i64) -> i64
called by 1: main
59func nx_fdb_outer_accumulate(G: *i64, row: *i64, d: i64) -> i64
called by 1: main
72func nx_fdb_frob_sq_diff(A: *i64, B: *i64, n: i64) -> i64
called by 1: main
83func main() -> i64