Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > OPERATOR NORMS:
Reports tagged with Operator norms:
TR18-037 | 21st February 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

#### Inapproximability of Matrix $p \rightarrow q$ Norms

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as $\|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}$ This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... more >>>

ISSN 1433-8092 | Imprint