{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidymtn7kpixuzxx4douzffefkgncvwpbyrebbzjr25l6dhtfxa52q",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkhv4lefgpc2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.22699v1",
  "publishedAt": "2026-04-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Prashanti Anderson",
    "Ainesh Bakshi",
    "Samuel Hopkins"
  ],
  "textContent": "**Authors:** Prashanti Anderson, Ainesh Bakshi, Samuel Hopkins\n\nGiven a matrix $A$, the goal of the entrywise low-rank approximation problem is to find $\\operatorname{argmin} \\|A-B\\|_p$ over all rank-$k$ matrices $B$, where $\\| \\cdot \\|_p$ is the entrywise $\\ell_p$ norm. When $p = 2$ this well-studied problem is solved by the singular value decomposition, but for $p \\neq 2$ the problem becomes computationally challenging. For every even $p > 2$ and every fixed $k$, we give the first polynomial-time approximation scheme for this problem, improving on the $(3 + \\varepsilon)$ approximation of Ban, Bhattiprolu, Bringmann, Kolev, Lee, and Woodruff, the bi-criteria approximation of Woodruff and Yasuda, and the additive approximation scheme of Anderson, Bakshi, and Hopkins. Prior algorithmic approaches based on sketching and column selection, which yielded a polynomial-time approximation scheme in the $p < 2$ setting, face concrete barriers when $p > 2$. Instead, we use the Sherali-Adams hierarchy of convex programs, and in so doing establish a blueprint for how to use convex hierarchies to design polynomial-time approximation schemes for continuous optimization problems. We use the same algorithmic strategy to give a new family of additive approximation algorithms for matrix $p \\rightarrow q$ norms, which are intimately related to small-set expansion and quantum information. In particular, we give the first nontrivial additive approximation algorithms in the regime $p < 2 < q$.",
  "title": "Entrywise Low-Rank Approximation and Matrix $p \\rightarrow q$ Norms via Global Correlation Rounding"
}