Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912293138202624 |
|---|---|
| author | Objois, Étienne Vladu, Adrian |
| author_facet | Objois, Étienne Vladu, Adrian |
| contents | We provide the first nearly-linear time algorithm for approximating $\ell_{q \rightarrow p}$-norms of non-negative matrices, for $q \geq p \geq 1$. Our algorithm returns a $(1-\varepsilon)$-approximation to the matrix norm in time $\widetilde{O}\left(\frac{1}{q \varepsilon} \cdot \text{nnz}(\boldsymbol{\mathit{A}})\right)$, where $\boldsymbol{\mathit{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 $\textit{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 $\widetilde{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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19553 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time Objois, Étienne Vladu, Adrian Data Structures and Algorithms Optimization and Control We provide the first nearly-linear time algorithm for approximating $\ell_{q \rightarrow p}$-norms of non-negative matrices, for $q \geq p \geq 1$. Our algorithm returns a $(1-\varepsilon)$-approximation to the matrix norm in time $\widetilde{O}\left(\frac{1}{q \varepsilon} \cdot \text{nnz}(\boldsymbol{\mathit{A}})\right)$, where $\boldsymbol{\mathit{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 $\textit{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 $\widetilde{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]. |
| title | Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2503.19553 |