精读笔记

Problem Setting

《Manifold-based Algorithms for the Hadamard Decomposition》（arXiv preprint / 2026）实际解决的是 HD 的数值优化与可扩展计算问题，而不是提出 HD 模型本身。HD 的吸引力在于两个 rank-r 矩阵的 Hadamard product 在 generic 情况下可达到 rank r^2，因此用约 2r(m+n) 参数实现接近 rank-r^2 的表达力。但这也带来优化难题：目标函数高度非凸，因子尺度不唯一，低秩约束与逐元素乘法纠缠，且朴素算法会生成 dense 中间矩阵。

以前方法卡在两个地方：一类直接在 W1,H1,W2,H2 上做梯度或 BCD，优化上可行但几何结构利用不足；另一类虽然能改善 dense 中小矩阵上的误差，但不能利用 X 的 sparsity，因为必须显式构造 X1=W1H1^T 和 X2=W2H2^T。本文的关键矛盾是：HD 的高表达力来自展开后的 r^2 交互，但如果计算仍停留在原始 Hadamard product 表达，就无法在大规模 sparse 数据上享受这种表达力。

Motivation

已有路线缺的是一个能同时解释 HD 表达力、约束结构和 sparse computation 的表示。作者的核心观察是 face-splitting product：Hadamard product of two low-rank matrices 可以精确写成一个 rank-r^2 factorization，但左右因子不是任意矩阵，而是每一行 reshape 后 rank≤1 的结构化矩阵。

这个观察自然引出 manifold-based algorithms：如果把可行集看成行级 rank-1 manifold 的乘积，那么投影、切空间投影和梯度更新都变成许多小 r×r 问题。真正的缺口不是“还没有另一个 optimizer”，而是此前没有把 HD 的非线性约束重写成一个适合 sparse least-squares 计算的结构化低秩因子空间。

Core Idea

论文真正的核心是把 HD 从 X≈(W1H1^T)∘(W2H2^T) 改写为 X≈WH^T，其中 W=W1•W2，H=H1•H2，W,H 各有 r^2 列，并且每一行都属于向量化 rank-1 矩阵的集合。这个转换不是记号变换，而是优化几何的重构：原问题的“两个低秩矩阵逐元素相乘”变成了“标准 least-squares matrix factorization + 行级 rank-1 manifold constraint”。

本质区别在于 inductive bias 的位置被移动了。prior 在四个低秩因子上直接施加低秩结构，算法必须通过 dense Hadamard product 感知误差；本文把所有 pairwise feature interactions 显式展开到 r^2 维，再用每行 rank-1 约束限制这些 interactions 必须可分解为两个 r 维 latent row 的 Kronecker product。这给了算法两个好处：一是可以直接使用 WH^T 的 sparse residual / Gram 计算；二是约束局部化，投影和流形更新都按行分解。

Method

方法层面最重要的不是三个算法的名字，而是它们对应的三种计算取舍。

Manopt 路线解决的是原始 HD 优化质量问题。它直接在 rank-r manifold M_r×M_r 上优化 X1∘X2，并提供 Euclidean gradient/Hessian 给 trust-region solver。它的核心变化是用二阶 Riemannian optimization 替代手写一阶更新，因此在 dense 中小规模问题上能得到更好局部解。但它仍需要 dense X1,X2，scalability 没有根本改善。

projBCD 解决的是 sparse computation。它在 W,H 表示下交替做 projected gradient，梯度就是标准 Ψ(W,H)=1/2||X-WH^T||_F^2 的 block gradient，投影通过逐行 rank-1 TSVD 完成。这个机制必要，因为普通 gradient step 会离开 face-splitting 可行集；投影把它拉回 HD 可表示的结构子空间。核心变化是每步计算可依赖 XH 或 X^TW，从而主项与 nnz(X) 成正比。

manBCD 试图避免投影成本和投影带来的离散跳跃。它构造在 B_{m,r} 上的 projected gradient flow，并把每一行对应的 rank-1 矩阵写成 μν yx^T，通过显式积分更新 μ,ν,x,y，使更新天然留在 manifold 上。它解决的是“保持可行性”的方式问题：不是先离开再投影，而是沿切空间走。

初始化是另一个关键机制。FS/FSL/FSR 都从 rank-r^2 TSVD 出发，再投影到 face-splitting 可行集。这一步实际上把最优线性 rank-r^2 子空间作为 warm start，再让 HD 结构吸收它；对非凸问题而言，这可能比后续 optimizer 的差异还重要。

Key Insight / Why It Works

最核心的 insight 是：HD 的优势可以被理解为一种受约束的 high-rank factorization，而不是普通 nonlinear matrix factorization。rank-r HD 能生成 generic rank-r^2 矩阵，但参数量只相当于 rank-2r TSVD；这中间的 gap 来自强结构化的 pairwise interactions。face-splitting representation 把这种隐式交互显式化，因此优化器不再需要通过原始 Hadamard product 间接学习交互。

为什么有效：第一，latent structure 对齐。许多数据矩阵，尤其图像和文档计数矩阵，可能不是低秩线性结构，而更像两个低维因素的乘性组合；HD 的逐元素乘法正好偏向这种 multiplicative interaction。第二，计算图更合理。WH^T 形式让误差、梯度和目标值可以用 X 的 sparse multiplication 和小 Gram matrix 表示，避免 dense reconstruction。第三，初始化把 TSVD 的全局信息注入到结构化可行集，使非凸优化从一个接近 rank-r^2 最优子空间的位置开始。

我认为本文最实质的贡献是 face-splitting manifold formulation 以及由此带来的 sparse algorithms，而不是 Manopt 本身。Manopt 是合理但相对直接的 Riemannian optimization 应用；projBCD/manBCD 的价值在于把 HD 从 dense nonlinear factorization 变成 sparse constrained factorization。rescaling、extrapolation、多次 block update 等明显是 engineering acceleration，重要但不是概念贡献。实验中部分增益可能主要来自 FS 初始化和 rank-r^2 TSVD warm start；文中没有完全剥离“表示更强”与“初始化更好”之间的贡献。

Relation To Prior Work

最接近的是 Ciaperoni et al. 的 gradient-based HD 和 Wertz et al. 的 BCD HD。它们都直接优化四个因子 W1,H1,W2,H2，目标函数相同，但没有把 HD 视为行 rank-1 constrained rank-r^2 factorization。因此 prior 的本质限制是计算路径仍依赖 dense Hadamard factors，难以利用 sparse X。

本文与标准 TSVD/low-rank approximation 的关系也很清楚：它不是在挑战 Eckart-Young，而是在不同模型类下比较参数效率。TSVD 在 rank-k 线性子空间里最优；HD 则用相近参数量进入一个通常 rank 更高但结构更强的非线性模型族。对真正 rank-2r 数据，TSVD 仍赢，这一点实验也验证了。

和 dynamical low-rank approximation 的关系主要体现在 manBCD：它借用切空间投影和 gradient flow 的思想，但对象从全局 rank-k manifold 变成了行级 rank-1 product manifold。这里的创新是结构迁移，而不是新的 ODE 数值分析。和一般 nonlinear matrix decomposition f(WH^T) 相比，HD 更特殊也更可解析，因为 Hadamard product 恰好能通过 face-splitting 线性化为 WH^T。

Dataset / Evaluation

实验覆盖 synthetic、dense image 和 sparse document matrices，基本能支撑论文的两个核心 claim：HD 在不少数据上比同参数 TSVD 更有压缩效率；新表示下的 projBCD/manBCD 能处理大 sparse 矩阵，而 Manopt/BCD 会遇到内存瓶颈。synthetic 设置也比较有诊断性：generic random、rank-2r、exact HD 三类分别测试表达力、与 TSVD 的边界、以及可恢复性。

但 evaluation 仍有明显限制。第一，评价指标几乎完全是 Frobenius reconstruction error，没有下游任务验证；对文档数据而言，重构误差未必等价于检索、分类或聚类质量。第二，时间预算和初始化选择会强烈影响非凸方法，论文报告“多个初始化中最好”的结果，这适合展示 best achievable performance，但不完全反映稳定部署成本。第三，rank 选择较小，尚未充分测试 r 增大后 r^4/r^6 项的真实瓶颈。第四，Manopt、BCD、projBCD、manBCD 之间的对比受 Matlab 实现、向量化程度和 memory behavior 影响，算法优劣与工程实现可能有混杂。

Limitation

最重要的理论限制是收敛性缺失。论文只能保证 restart 后 objective non-increasing，因此函数值收敛；但 iterates 是否收敛、是否到达 stationary point、在尺度不唯一和非紧 manifold 下如何规约，文中未解决。这个不是小问题，因为 HD 的非唯一性非常强，包括全局缩放和 rank-1 Hadamard reweighting。

scalability 也有上限。虽然 sparse 主项是 O(nnz(X) r^2)，但 Gram 和 Lipschitz 相关项有 O((m+n)r^4+r^6)，投影还有逐行小 SVD。只要 r 稍大，所谓 rank-r^2 表达力会变成计算负担。因此本文方法适合“小 r 高表达”的压缩 regime，不适合大 latent dimension。

增益归因不完全清楚。HD 相比 TSVD 的优势可能来自 multiplicative inductive bias，也可能来自允许 effective rank 到 r^2；FS 初始化本身先用了 rank-r^2 TSVD，再投影，这可能贡献很大。文中没有充分说明如果不用 TSVD warm start、或者严格控制所有算法的 initialization information，HD 算法本身还能稳定获得多少增益。

此外，HD 的模型假设较强：每个 r^2 维 row embedding 必须是两个 r 维向量的 Kronecker/outer product。这个假设在图像和文本压缩上表现不错，但它是否对应真实生成机制并不确定。对低秩数据，HD 不如 TSVD；这说明它不是 universally better，而是适合有乘性潜结构的数据。

Takeaway

• 1. HD 最值得记住的不是“两个低秩矩阵相乘”，而是“带行 rank-1 约束的 rank-r^2 factorization”。
• 这个视角比原始定义更适合算法设计。
• 2. face-splitting representation 是可迁移 insight：很多看似 nonlinear 的矩阵模型，如果能展开成线性 factorization 加局部结构约束，就能同时获得表达力和 sparse computation。
• 3. 初始化在结构化非凸分解中可能比 optimizer 更关键。

一句话总结

这篇论文把 Hadamard decomposition 从 dense nonlinear factorization 重新表述为行 rank-1 流形约束下的 rank-r^2 低秩分解，并由此给出更适合 sparse 大矩阵的优化算法，是一次以结构重参数化驱动可计算性的工作。