手写非负矩阵分解（NMF / Non-negative Matrix Factorization） —— Lee & Seung, Nature 399, 788 (1999)。
零依赖、零构建、单文件 HTML。打开 index.html 即可运行：内联引擎 + 实时不变量自检面板 + 无头可验证。
X ≈ W · H X ≥ 0 (m×n)
W ≥ 0 (m×K) 基向量 / parts
H ≥ 0 (K×n) 系数 / 占比
与 PCA / SVD 的根本差异：分解只允许加，不允许减。因此 W 的列可以解释为「部件」，H 可以解释为「每个样本由哪些部件、各占多少构成」。SVD 的基向量有正有负（本仓库实测 32.4% 为负），拿不出这种解释。
全部手写，无任何数学库。
| 模块 | 内容 |
|---|---|
| 目标函数 | Frobenius F = ‖X − WH‖²_F；KL 散度 D(X‖WH) = Σ X∘log(X⊘WH) − X + WH |
| 乘法更新 · Frobenius | H ← H∘(WᵀX)⊘(WᵀWH)；W ← W∘(XHᵀ)⊘(WHHᵀ) |
| 乘法更新 · KL | H ← H∘(Wᵀ(X⊘WH))⊘(Wᵀ1)；W ← W∘((X⊘WH)Hᵀ)⊘(1Hᵀ) |
| ALS | 交替非负最小二乘，子问题用投影梯度（步长 1/L，L=‖AᵀA‖₂ 由幂迭代估计） |
| 截断 SVD | 幂迭代 + 收缩（deflation），每步做修正 Gram–Schmidt 重正交；误差直接取收缩后残差范数 |
| 初始化 | 随机（严格正，避免「分量死亡」）/ NNDSVD-lite（用 top-K 奇异三元组播种） |
| 最优性度量 | 投影梯度（Lin 2007）：PG_ik = ∇_ik if Z_ik>0 else min(0,∇_ik)；KKT ⟺ PG≡0 |
| 数据 | 合成「光谱混合」模型：W₀ 为平滑高斯峰，H₀ 每列 1~3 个活跃分量 |
Lee–Seung 的更新不是启发式，而是 majorize–minimize（MM）：构造辅助函数 G(W, Wᵗ) ≥ F(W) 且 G(Wᵗ, Wᵗ) = F(Wᵗ)，对其最小化得到闭式解 —— 恰好就是上式。因此 F 严格不增。
这使「目标函数单调不增」成为一条可断言的定理，而不是经验观察（本仓库实测：Frobenius maxΔ = -4.4e-7，KL maxΔ = -1.4e-9，全程无一上升）。
W ← W∘(…) 意味着 W_ik = 0 将永远为 0。
- 好处：保持稀疏结构；
- 代价：若某行基向量被初始化成全零，该分量永久死亡，再也不会复活。
本仓库在 _smoke.js 中用强制置零的行做了显式断言，并让随机初始化保持严格正。
node _smoke.js # 34 条数学不变量
node _uicheck.js # 18 条 UI 接线检查（DOM stub）
node _probe.js # 真实数值（人工核对用，不参与断言）| 类别 | 不变量 | 实测 |
|---|---|---|
| 非负 | X≥0 ⟹ W,H 全程 ≥0（muF / muKL / ALS） | 6.5e-54 / 4.7e-25 / 0 |
| 单调性 | Frobenius 目标单调不增（MM 定理） | maxΔ = -4.39e-7 |
| KL 目标单调不增 | maxΔ = -1.38e-9 |
|
| 最优性 | KKT 投影梯度 → 0（ALS） | 4.42e-9 |
| MU 与 ALS 收敛到同一目标值 | 相对差 2.1e-6 |
|
对偶可行 min ∇ ≥ 0 |
-2.7e-9 |
|
| 结构 | 乘法更新保值零元 | 0 违例 |
| 精确恢复 | 秩-1 X = uvᵀ，K=1 |
relF = 3.05e-16 |
可分离 X = W₀[I|B]，K=3 |
relF = 1.65e-12，max|corr| = 0.9910 |
|
| 约束对照 | NMF 误差 ≥ 截断 SVD 误差（可行集更小） | K=1,2,4,6 全部成立 |
| SVD 自洽 | 显式重构误差 == 报告的 err | 完全相等 |
奇异向量正交 UᵀU=I, VᵀV=I |
2.08e-16 |
|
| Eckart–Young：SVD 秩-K ≤ 随机秩-K | 18.06 vs 61.18 |
|
| 对称性 | 确定性（同种子逐位一致） | 逐位相同 |
尺度不变 W·s, H/s ⟹ WH 不变 |
4.44e-16 |
|
| 列置换等变（W 不变，H 同步置换） | 3.7e-14 / 6.7e-15 |
|
| NNLS 子问题 | KKT：Z≥0，∇≥-tol，Z∘∇=0 |
1.9e-11 |
| NNLS 目标 ≤ 裁剪最小二乘目标 | 95.025 vs 96.939 |
UI 检查额外覆盖：ALS / KL / random init / K=1 / K=10 / σ=0.4 六种配置下自检面板 9/9 全绿。
基向量恢复（置换 + 尺度不变，|corr|）：w0→0.9997, w1→1.0000, w2→0.9999, w3→1.0000 —— 在 σ=0.02 噪声下几乎完美还原真峰。
MU 与 ALS 的收敛差距（值得记住）
| 算法 | 迭代 | relF | KKT(PG) |
|---|---|---|---|
| MU-Frobenius | 1200 | 0.029563 | 6.13e-4 |
| MU-KL | 1200 | 0.030316 | 9.72e-4 |
| ALS | 1200 | 0.029543 | 5.37e-9 |
relF 一致到 1e-6（同一最优解），但 MU 的线性收敛速率接近 1，KKT 残差差 5 个数量级。工程上：要精度用 ALS，要简单/严格单调/内存省用 MU。
非负约束的代价（NMF relF − 截断 SVD relF ≥ 0 恒成立）
| K | NMF | SVD | 代价 |
|---|---|---|---|
| 1 | 0.60488 | 0.60488 | ≈ 0 |
| 2 | 0.45879 | 0.45638 | 0.00241 |
| 3 | 0.32041 | 0.31617 | 0.00424 |
| 4 | 0.02954 | 0.02953 | 0.00001 |
K=1 时代价严格为 0，这不是巧合：由 Perron–Frobenius，非负矩阵的首奇异向量可同取非负（实测 min(u₁)=2.6e-2 > 0、min(v₁)=1.3e-2 > 0），于是非负约束完全不咬人 —— 这是把「约束代价 ≥ 0」这条断言钉死在 K=1 的理论支点。
K 选择：真 K=4 处出现明显肘部（K=3→4 relF 从 0.320 跌到 0.030，K=5,6 收益骤减）。无监督选 K 的实践准则，本仓库把它画出来了。
健壮性：6 个种子（1/7/42/99/2026/123456）relF 全部 0.02954，离散度为零 —— 与上一轮 transformer-forge 换 seed 掉到 56~78% 形成对照：NMF 目标在低秩问题上好得多。
| 文件 | 说明 |
|---|---|
index.html |
全部交付物：<script id="engine"> 暴露 globalThis.NMF，<script id="ui"> 负责可视化 |
_smoke.js |
34 条无头数学不变量（原生 Node，抽出 engine 执行） |
_uicheck.js |
18 条 UI 接线检查（DOM stub + vm，能抓到 smoke 抓不到的 UI bug） |
_probe.js |
真实数值探针：收敛对照 / 约束代价 / 符号性 / ASCII 热图 / 恢复质量 / 肘部曲线 |
LICENSE |
MIT |
-
KL 更新破坏单调性：
R = X⊘WH只算了一次，更新 H 后没重算就用于更新 W —— 用的是陈旧比值，不是合法块更新。表现：KL 目标maxΔ = +296（单调性断言立刻红）。修法：两次块更新各自重算WH与R。 -
KKT 度量在精确拟合时退化为 0/0：原用
max|W∘∇| / max|∇|。当F→0（无噪且 K=真秩）时∇→0，比值由浮点噪声主导，轨迹在0与9.8e-4间乱跳。修法：改用 投影梯度（Lin 2007），并用‖X‖·‖H‖归一化使其无量纲。 -
幂迭代未收敛导致「约束代价」出现负值：
max|offdiag|=9.7e-7的正交性漂移，加上用‖X‖²−Σσ²捷径算误差，使 K=1 出现-0.00000—— 而NMF ≥ SVD理论上不可能违反。修法：加修正 Gram–Schmidt 重正交、加收敛判据、误差改为收缩后残差范数（精确）。修后 gap =-1.11e-15（机器精度）。
另有两处是测试自身的 bug，值得单独记：最小化问题的单调性断言应查最大增量（maxΔ ≤ 0），我却写成查 minΔ，把「最大的一次下降」误报成违例。
MIT © 晨星