Book ; Online: Estimating the matrix $p \rightarrow q$ norm
2023
Abstract: The matrix $p \rightarrow q$ norm is a fundamental quantity appearing in a variety of areas of mathematics. This quantity is known to be efficiently computable in only a few special cases. The best known algorithms for approximately computing this ... ...
Abstract | The matrix $p \rightarrow q$ norm is a fundamental quantity appearing in a variety of areas of mathematics. This quantity is known to be efficiently computable in only a few special cases. The best known algorithms for approximately computing this quantity with theoretical guarantees essentially consist of computing the $p\to q$ norm for $p,q$ where this quantity can be computed exactly or up to a constant, and applying interpolation. We analyze the matrix $2 \to q$ norm problem and provide an improved approximation algorithm via a simple argument involving the rows of a given matrix. For example, we improve the best-known $2\to 4$ norm approximation from $m^{1/8}$ to $m^{1/12}$. This insight for the $2\to q$ norm improves the best known $p \to q$ approximation algorithm for the region $p \le 2 \le q$, and leads to an overall improvement in the best-known approximation for $p \to q$ norms from $m^{25/128}$ to $m^{3 - 2 \sqrt{2}}$. |
---|---|
Keywords | Computer Science - Data Structures and Algorithms ; Mathematics - Functional Analysis ; 15A60 ; 65F35 ; 68W25 |
Subject code | 518 |
Publishing date | 2023-11-13 |
Publishing country | us |
Document type | Book ; Online |
Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.