File size: 6,628 Bytes
515b676 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | """Correctness gates: re-derive quantities the paper (or classical theory)
already establishes, and assert them before interpreting anything else."""
import json
import numpy as np
import rdpg
OUT = {}
def gate_eig_residual(rng):
"""LAPACK eigendecomposition of A is exact to machine precision."""
n, r = 800, 5
A, X = rdpg.weighted_rdpg(n, r, rng)
s, U = rdpg.full_spectrum(A)
res = float(np.max(np.abs(A - (U * s) @ U.T)))
orth = float(np.max(np.abs(U.T @ U - np.eye(n))))
return {"max_abs_recon_residual": res, "max_abs_orthonormality_residual": orth,
"n": n, "pass": res < 1e-9 and orth < 1e-9}
def gate_dirichlet_moments(rng):
"""For X_i ~ Dir(1,1,1,1,1), M = E[x x^T] = (I + J)/30 exactly, so the
non-zero eigenvalues of P = X X^T obey s_1/n -> 1/5, s_2..s_5/n -> 1/30.
This pins the constant in Assumption A4 (s_j asymp rho_n n) and shows that
the paper's own simulation design has a 4-fold degenerate population
eigenvalue (Assumptions A3/A6 hold only through O(sqrt(n)) fluctuations)."""
r = 5
M_theory = (np.eye(r) + np.ones((r, r))) / 30.0
ev_theory = np.sort(np.linalg.eigvalsh(M_theory))[::-1]
rows = []
for n in [2000, 20000, 200000]:
X = rdpg.dirichlet_latent(n, r, rng)
M_emp = X.T @ X / n
ev_emp = np.sort(np.linalg.eigvalsh(M_emp))[::-1]
rows.append({"n": n,
"max_abs_moment_err": float(np.max(np.abs(M_emp - M_theory))),
"eigs_emp": ev_emp.tolist()})
return {"M_theory_eigs": ev_theory.tolist(), "rows": rows,
"degenerate_multiplicity": 4,
"pass": rows[-1]["max_abs_moment_err"] < 5e-3}
def gate_eckart_young(rng):
"""Lemma 2.1 (k<0 branch) is an Eckart-Young statement. With E = 0 the
d-dimensional ASE IS the rank-d truncated eigendecomposition of P, so
min_W ||Xhat^o W - rho^{1/2}X||_F must EQUAL sqrt(sum_{j>d} s_j) exactly,
and the (2,inf) lower bound of Lemma 2.1 must hold."""
n, r, rho = 1500, 5, 1.0
X = rdpg.dirichlet_latent(n, r, rng)
P = rho * (X @ X.T)
s, U = rdpg.full_spectrum(P)
s_nz = np.sort(np.linalg.eigvalsh(rho * (X.T @ X)))[::-1] # exact non-zero eigs
rows = []
for d in [1, 2, 3, 4]:
Xh = rdpg.ase_from_spectrum(s, U, d)
e2i, D = rdpg.err_2inf(Xh, np.sqrt(rho) * X)
fro = float(np.linalg.norm(D))
fro_theory = float(np.sqrt(s_nz[d:].sum()))
bound = float(np.sqrt(s_nz[d:].sum() / n)) # Lemma 2.1
rows.append({"d": d, "k": d - r, "frob_measured": fro,
"frob_eckart_young": fro_theory,
"rel_frob_residual": abs(fro - fro_theory) / fro_theory,
"err_2inf": e2i, "lemma21_lower_bound": bound,
"ratio_2inf_over_bound": e2i / bound})
return {"n": n, "rows": rows,
"max_rel_frob_residual": max(x["rel_frob_residual"] for x in rows),
"min_ratio": min(x["ratio_2inf_over_bound"] for x in rows),
"pass": max(x["rel_frob_residual"] for x in rows) < 1e-10
and min(x["ratio_2inf_over_bound"] for x in rows) >= 1.0}
def gate_procrustes(rng):
"""W = U V^T from SVD(Xhat^T X) solves min_{W in O} ||Xhat W - X||_F.
Verified by (a) first-order optimality: W^T Xhat^T X is symmetric PSD,
(b) beating 20000 random rotations."""
n, r, d = 400, 5, 7
A, X = rdpg.weighted_rdpg(n, r, rng)
s, U = rdpg.full_spectrum(A)
Xh = rdpg.ase_from_spectrum(s, U, d)
Xp = np.hstack([X, np.zeros((n, d - r))])
Uu, sv, Vt = np.linalg.svd(Xh.T @ Xp)
W = Uu @ Vt
best = float(np.linalg.norm(Xh @ W - Xp))
Msym = W.T @ (Xh.T @ Xp)
sym_err = float(np.max(np.abs(Msym - Msym.T)))
psd_min = float(np.min(np.linalg.eigvalsh((Msym + Msym.T) / 2)))
worst = 0.0
for _ in range(20000):
Q, _ = np.linalg.qr(rng.standard_normal((d, d)))
worst = max(worst, best - float(np.linalg.norm(Xh @ Q - Xp)))
return {"frob_at_procrustes": best, "symmetry_residual": sym_err,
"min_eig_of_WtXhatTX": psd_min,
"best_random_rotation_improvement": worst,
"pass": sym_err < 1e-9 and psd_min > -1e-9 and worst <= 1e-9}
def gate_semicircle_edge(rng):
"""||E|| / (2 sigma sqrt(n)) -> 1 (Wigner edge). The paper bounds the
trailing ASE eigenvalues by ||E|| (Sec. 2.1), so this constant matters."""
rows = []
for n in [500, 1000, 2000, 4000]:
vals = []
for _ in range(3):
E = rdpg.sym_noise(n, rng, "normal", 1.0)
vals.append(float(np.linalg.norm(E, 2)))
rows.append({"n": n, "opnorm": float(np.mean(vals)),
"ratio_to_2sqrtn": float(np.mean(vals)) / (2 * np.sqrt(n))})
return {"rows": rows, "final_ratio": rows[-1]["ratio_to_2sqrtn"],
"pass": abs(rows[-1]["ratio_to_2sqrtn"] - 1.0) < 0.05}
def gate_signal_incoherence(rng):
"""Corollary B.3.1 / Assumption A1: ||U_{1:r}||_{2,inf} <~ 1/sqrt(n).
We report the constant sqrt(n)*||U_{1:r}||_{2,inf}, which must not grow."""
rows = []
for n in [500, 1000, 2000, 4000, 8000]:
X = rdpg.dirichlet_latent(n, 5, rng)
P = X @ X.T
s, U = rdpg.full_spectrum(P)
c = rdpg.two_inf(U[:, :5]) * np.sqrt(n)
rows.append({"n": n, "sqrtn_times_2inf": float(c)})
return {"rows": rows,
"drift": rows[-1]["sqrtn_times_2inf"] / rows[0]["sqrtn_times_2inf"],
"pass": rows[-1]["sqrtn_times_2inf"] < 3 * rows[0]["sqrtn_times_2inf"]}
def jsonable(o):
if isinstance(o, dict):
return {k: jsonable(v) for k, v in o.items()}
if isinstance(o, (list, tuple)):
return [jsonable(v) for v in o]
if isinstance(o, (np.bool_, bool)):
return bool(o)
if isinstance(o, (np.integer,)):
return int(o)
if isinstance(o, (np.floating,)):
return float(o)
return o
if __name__ == "__main__":
rng = np.random.default_rng(20260728)
OUT["matmul_sanity"] = rdpg.matmul_sanity()
OUT["eig_residual"] = gate_eig_residual(rng)
OUT["dirichlet_moments"] = gate_dirichlet_moments(rng)
OUT["eckart_young"] = gate_eckart_young(rng)
OUT["procrustes"] = gate_procrustes(rng)
OUT["semicircle_edge"] = gate_semicircle_edge(rng)
OUT["signal_incoherence"] = gate_signal_incoherence(rng)
OUT["all_pass"] = bool(all(v["pass"] for v in OUT.values() if isinstance(v, dict)))
OUT = jsonable(OUT)
with open("outputs/gates.json", "w") as f:
json.dump(OUT, f, indent=1)
print(json.dumps(OUT, indent=1))
|