我们提出了一种算法，能够在 $\widetilde{O}(s^{3/2}\log(1/\varepsilon))$ 时间内，以误差 $\varepsilon$ 计算非负矩阵（非零元素数为 $s$）的 $p \to q$ 范数，适用于任意 $p \ge q \ge 1$。此前最快的算法时间复杂度为 $\widetilde{O}(s/\varepsilon)$（Objois 与 Vladu, 2026），在追求高精度时明显更慢。
核心思路是将问题表述为在幂锥积上的线性优化，并在内部点法（IPM）中巧妙使用拉普拉斯求解器。IPM 的牛顿步可以通过求解一个 Schur 补矩阵的拉普拉斯系统得到，该系统在减去一个秩为 2 的矩阵后仍保持拉普拉斯结构。
实现层面，我们将上述理论转化为可运行的代码，并在多种基准任务上与商业求解器 MOSEK 对比。实验表明，在相同精度要求下，我们的实现可比 MOSEK 快至 20 倍，且在稀疏度较高的实例中表现尤为突出。
$$\text{复杂度} = \widetilde{O}\bigl(s^{3/2}\log(1/\varepsilon)\bigr)$$
点评：该算法通过拉普拉斯求解器与 IPM 的结合，突破了传统 $\widetilde{O}(s/\varepsilon)$ 的瓶颈，为稀疏非负矩阵范数计算提供了实用且高效的工具。