- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Approximability of Matrix Norms
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Approximability of Matrix Norms Tulsiani, Madhur
Description
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.
Item Metadata
| Title |
Approximability of Matrix Norms
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2018-08-13T17:08
|
| Description |
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.
|
| Extent |
23.0
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Toyota Technological Institute at Chicago
|
| Series | |
| Date Available |
2019-03-27
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0377623
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Researcher
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International