We present an algorithm that computes the $p \to q$ norm of a non‑negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in $\widetilde{O}(s^{3/2}\log(1/\varepsilon))$ time, for any $p \ge q \ge 1$. The previously fastest method runs in $\widetilde{O}(s/\varepsilon)$ (Objois & Vladu, 2026) and becomes slower when high precision is required.
The key idea is to formulate the task as a linear optimization over a product of power cones and to embed Laplacian solvers inside an Interior Point Method (IPM). The Newton updates of the IPM reduce to solving a Laplacian system in a Schur complement after subtracting a rank‑2 matrix, preserving the Laplacian structure.
On the implementation side, we translate the theory into a practical codebase and benchmark it against the commercial solver MOSEK on various tasks. Results show that, for the same accuracy, our implementation can be up to 20× faster than MOSEK, especially on highly sparse instances.
$$\text{Complexity}=\widetilde{O}\bigl(s^{3/2}\log(1/\varepsilon)\bigr)$$
Review: By coupling Laplacian solvers with IPM, the algorithm breaks the $\widetilde{O}(s/\varepsilon)$ barrier and offers a fast, accurate tool for sparse non‑negative matrix norm computation.