sketch_freq_directions_vs_topnorm_bench.nx
buildroot/runtime/sketch_freq_directions_vs_topnorm_bench.nx
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
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
structs
| none |
consts
| 40 | const NX_FDB_Q14: i64 = 16384 |
| 41 | const NX_FDB_D: i64 = 4 |
| 42 | const NX_FDB_L: i64 = 3 |
| 43 | const NX_FDB_N: i64 = 50 |
| 45 | const NX_FDB_LCG_A: i64 = 1103515245 |
| 46 | const NX_FDB_LCG_C: i64 = 12345 |
| 47 | const NX_FDB_LCG_MOD: i64 = 0x7FFFFFFF |
functions
| 49 | func nx_fdb_row_norm_sq(row: *i64, d: i64) -> i64 called by 1: main |
| 59 | func nx_fdb_outer_accumulate(G: *i64, row: *i64, d: i64) -> i64 called by 1: main |
| 72 | func nx_fdb_frob_sq_diff(A: *i64, B: *i64, n: i64) -> i64 called by 1: main |
| 83 | func main() -> i64 |