Entrywise Low-Rank Approximation and Matrix p → q p\rightarrow q Norms via Global Correlation Rounding
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins · 2026
Read Entrywise Low-Rank Approximation and Matrix p → q p\rightarrow q Norms via Global Correlation Rounding by Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22699.txt.
Introduction
Anderson, Bakshi, and Hopkins tackle entrywise low-rank approximation: finding the closest low-rank matrix under an entrywise norm. Singular value decomposition solves this only for the squared case. For every even exponent above two and any fixed rank, they give the first approximation scheme, built on the Sherali-Adams hierarchy rather than sketching or column choice. The same strategy yields new additive approximations for matrix norms linked to small-set expansion and quantum information.
Catalog record
| CREATOR | Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 215896 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22699