Approximating $q\to p$ Norms of Non-Negative Matrices in Nearly-Linear Time

Abstract

We provide the first nearly-linear time algorithm for approximating ${\ell }_{q\to p}$-norms of non-negative matrices, for $q\ge p\ge 1$. Our algorithm returns a $(1-\epsilon )$-approximation to the matrix norm in time $\tilde{O}\left(\frac{1}{q\epsilon }\cdot \text{nnz}(A)\right)$, where $A$ is the input matrix, and improves upon the previous state of the art, which either proved convergence only in the limit [Boyd '74], or had very high polynomial running times [Bhaskara-Vijayraghavan, SODA '11]. Our algorithm is extremely simple, and is largely inspired from the coordinate-scaling approach used for positive linear program solvers. We note that our algorithm can readily be used in the [Englert-Räcke, FOCS '09] to improve the running time of constructing $O(\log n)$-competitive ${\ell }_p$-oblivious routings. We thus complement this result with a simple cutting-plane based scheme for computing $\text{optimal}$ oblivious routings in graphs with respect to any monotone norm. Combined with state of the art cutting-plane solvers, this scheme runs in time $\tilde{O}(n^6{m}^3)$, which is significantly faster than the one based on Englert-Räcke, and generalizes the ${\ell }_{\infty }$ routing algorithm of [Azar-Cohen-Fiat-Kaplan-Räcke, STOC '03].