We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

(In)Approximability of Matrix Norms

Formal Metadata

Title
(In)Approximability of Matrix Norms
Alternative Title
Approximability of Matrix Norms
Title of Series
Number of Parts
17
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
I will talk aboutthe problem of computing the operator norm of a matrix mapping vectors in the space l_p to l_q, for different values of p and q. This problem generalizes the spectral norm of a matrix (p=q=2) and the Grothendieck problem (p=\infty, q=1), and has been widely studied in various reigmes. When p greater than or equal to q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 lies between p and q, and is hard to approximate within almost polynomial factors otherwise. The regime when q is greater than p, known as the _hypercontractive case_, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by [Barak et al., STOC'12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation was known for these problems for any p < q. We study the hardness of approximating matrix norms in both the above cases. We prove the following results: - We show that for any p < q, the operator norm of a given matrix is hard to approximate within almost polynomial factors, when 2 does not lie between p and q. This suggests that similar to the non-hypercontrative setting, the case when 2 does not lie between p and q may be qualitatively different. - We also obtain new (constant factor) hardness results in the non-hypercontractive case when q <= 2 <= p. The bounds we obtain are known to be tight in the cases when either p or q equals 2.