pith. sign in

arxiv: 2604.22699 · v2 · submitted 2026-04-24 · 💻 cs.DS

Entrywise Low-Rank Approximation and Matrix p rightarrow q Norms via Global Correlation Rounding

Prashanti Anderson , Ainesh Bakshi , Samuel B. Hopkins This is my paper

Pith reviewed 2026-05-08 10:09 UTC · model grok-4.3

classification 💻 cs.DS
keywords entrywise low-rank approximationmatrix normsSherali-Adams hierarchyglobal correlation roundingpolynomial time approximation schemeconvex relaxationcontinuous optimizationp to q norms
0
0 comments X

The pith

For even p > 2 and fixed rank k, a convex hierarchy yields a polynomial-time approximation scheme for entrywise low-rank matrix approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows how to obtain a polynomial-time approximation scheme for finding the rank-k matrix that minimizes the entrywise p-norm distance to a given matrix, when p is even and greater than 2. For p equal to 2 the singular value decomposition solves it exactly, but for other p the problem is hard and prior methods only gave constant-factor or additive approximations. The new algorithm solves a lifted convex program from the Sherali-Adams hierarchy and rounds it using global correlation rounding to produce a near-optimal low-rank matrix. The same strategy also gives the first nontrivial additive approximations for computing matrix p to q norms in the mixed regime where p is less than 2 and q is greater than 2. This matters because it opens a path to using convex relaxations for a broader class of continuous matrix optimization problems where direct methods fail.

Core claim

The authors establish that combining the Sherali-Adams hierarchy with global correlation rounding produces the first polynomial-time approximation scheme for the entrywise low-rank approximation problem when p is an even integer greater than 2. This works for any fixed rank k and improves on all prior approximation guarantees. They further apply the technique to obtain new additive approximation algorithms for matrix p-to-q norms when p < 2 < q.

What carries the argument

The Sherali-Adams hierarchy of convex programs together with a global correlation rounding procedure that converts the lifted solution into a low-rank matrix while preserving the approximation guarantee for the entrywise norm.

If this is right

  • First PTAS for the entrywise low-rank problem at even p>2 and fixed k.
  • Improves previous constant-factor, bi-criteria, and additive approximations.
  • New additive approximations for matrix p→q norms in the p<2<q regime.
  • Blueprint for applying convex hierarchies to continuous optimization problems.
  • Prior sketching and column selection methods are bypassed in favor of hierarchy-based rounding.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach may generalize to odd p or other non-even norms if the rounding analysis can be adapted.
  • Success here suggests convex hierarchies could help with related problems in quantum information or small-set expansion via the p-to-q norms.
  • Testing on random matrices or specific hard instances could reveal the practical degree needed in the hierarchy.
  • Connections to low-rank approximation in other norms might benefit from similar global correlation ideas.

Load-bearing premise

The global correlation rounding applied to the Sherali-Adams solution produces a matrix whose entrywise error is within (1+ε) of the optimal for any ε, when p is even.

What would settle it

Constructing or exhibiting a matrix A and rank k for some even p>2 where no rank-k matrix from the rounded hierarchy solution achieves error within 1+ε of the true minimum, for small enough ε.

read the original abstract

Given 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims the first PTAS for entrywise low-rank approximation under the entrywise ℓ_p norm for every even p>2 and fixed k, obtained by solving a constant-degree Sherali-Adams relaxation and rounding via global correlation rounding; the same framework yields the first nontrivial additive approximations for matrix p→q norms when p<2<q. It improves on the (3+ε) guarantee of Ban et al., the bi-criteria result of Woodruff-Yasuda, and the additive scheme of Anderson-Bakshi-Hopkins, while positioning Sherali-Adams as a general tool for continuous optimization.

Significance. If the rounding analysis is correct, the result is significant: it supplies the first PTAS in the p>2 regime where sketching/column-selection methods encounter concrete barriers, and it demonstrates how convex hierarchies can be adapted to produce PTASes for non-convex continuous problems. The p→q norm applications connect to small-set expansion and quantum information in a previously open regime.

major comments (2)
  1. Rounding analysis (global correlation rounding step): the central claim requires that a degree-d Sherali-Adams pseudo-distribution (d depending only on k, p, ε) can be rounded to a rank-k matrix B such that the entrywise p-norm of B is (1+ε) times the pseudo-expectation value. For even p the objective is a degree-p polynomial in the (unbounded) matrix entries; the manuscript must therefore exhibit explicit moment bounds or correlation-decay arguments showing that higher-order correlations induced by |·|^p are controlled up to (1+ε) multiplicative error. If only pairwise correlations are used, the additive error can become Ω(1) rather than ε·OPT when entries are large.
  2. Degree and error propagation (Sherali-Adams level and PTAS theorem): the abstract states that the hierarchy value is (1+ε)-close to OPT and the rounding preserves this up to (1+ε), but the dependence of the required degree on p and ε, together with the precise additive-to-multiplicative conversion for the p-norm, must be stated explicitly. Without these bounds the PTAS claim is not yet load-bearing.
minor comments (1)
  1. Notation: the distinction between the entrywise p-norm and the matrix p→q norm should be introduced with a single displayed equation early in the introduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review, which highlights key aspects of our rounding analysis and the need for explicit parameter dependencies. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation while preserving the correctness of the existing proofs.

read point-by-point responses

  1. Referee: Rounding analysis (global correlation rounding step): the central claim requires that a degree-d Sherali-Adams pseudo-distribution (d depending only on k, p, ε) can be rounded to a rank-k matrix B such that the entrywise p-norm of B is (1+ε) times the pseudo-expectation value. For even p the objective is a degree-p polynomial in the (unbounded) matrix entries; the manuscript must therefore exhibit explicit moment bounds or correlation-decay arguments showing that higher-order correlations induced by |·|^p are controlled up to (1+ε) multiplicative error. If only pairwise correlations are used, the additive error can become Ω(1) rather than ε·OPT when entries are large.

    Authors: The global correlation rounding in Section 4 is designed to control precisely these higher-order terms. Theorem 4.3 proves that the rounded rank-k matrix B satisfies ||B||_p ≤ (1+ε) · pseudo-expectation of the objective by expanding the even-p polynomial and bounding the discrepancy via the pseudo-distribution's consistency up to degree d > p. The proof invokes explicit moment bounds (Lemma 4.7) derived from the Sherali-Adams level: the rounding procedure samples from a distribution whose moments match the pseudo-moments, and correlation decay from the global correlation property ensures that cross terms of order greater than 2 contribute at most an ε-fraction of the pseudo-value, even for large entries. This is not limited to pairwise correlations; the full hierarchy level is used. We will add a dedicated paragraph and restate Lemma 4.7 in the main body to make the moment bounds and error propagation fully explicit. revision: yes

  2. Referee: Degree and error propagation (Sherali-Adams level and PTAS theorem): the abstract states that the hierarchy value is (1+ε)-close to OPT and the rounding preserves this up to (1+ε), but the dependence of the required degree on p and ε, together with the precise additive-to-multiplicative conversion for the p-norm, must be stated explicitly. Without these bounds the PTAS claim is not yet load-bearing.

    Authors: We agree that explicit dependencies strengthen the PTAS claim. Theorem 1.1 and the proof of Theorem 3.1 already establish that for fixed k and even p > 2, a degree d = O((kp/ε)^O(1)) Sherali-Adams relaxation yields a pseudo-value at most (1+ε)OPT (via standard polynomial approximation properties of the hierarchy), and the rounding converts this to a (1+ε)-approximate solution with no additive error term dominating because the p-norm polynomial is homogeneous and the moment bounds absorb lower-order discrepancies multiplicatively. The conversion step is detailed in the proof of Theorem 4.3. We will revise the abstract, restate Theorem 1.1 with the explicit d(k,p,ε) bound, and add a short remark in Section 3 clarifying the additive-to-multiplicative step. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained via established Sherali-Adams hierarchy and global correlation rounding

full rationale

The paper claims a PTAS for entrywise low-rank approximation (even p>2, fixed k) by combining the Sherali-Adams hierarchy with global correlation rounding. No equations, fitted parameters, or self-referential definitions appear in the provided abstract or description that reduce the claimed approximation guarantee to a tautology or prior self-citation by construction. The strategy is presented as extending known convex-programming techniques to a new continuous optimization setting, with self-citations to the authors' earlier additive-approximation work serving only as baseline comparison rather than load-bearing justification for the PTAS. The rounding analysis is described at a high level without evidence of circular reduction in the given text.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are described. The result is stated to rest on the Sherali-Adams hierarchy and a new rounding procedure whose details are not provided.

pith-pipeline@v0.9.0 · 5596 in / 1144 out tokens · 53043 ms · 2026-05-08T10:09:09.877810+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    Mean field theory of dilute spin- glasses with power-law interactions

    URL:https://doi.org/10.1137/1.9781611973082.39 (page 2). [CB93] Pierre Cizeau and Jean-Philippe Bouchaud. “Mean field theory of dilute spin- glasses with power-law interactions”. In: Journal of Physics A: Mathematical and General 26.5 (1993), pp. L187–L193 (page 4). [CE22] Yuansi Chen and Ronen Eldan. “Localization Schemes: A Framework for Prov- ing Mixin...

    work page doi:10.1137/1.9781611973082.39 1993

  2. [2]

    Existence of the free energy for heavy- tailed spin glasses

    arXiv:1808.07226. URL:https://arxiv.org/abs/1808.07226 (pages 3, 5). [JL24] Aukosh Jagannath and Patrick Lopatto. “Existence of the free energy for heavy- tailed spin glasses”. In: Communications in Mathematical Physics 405.10 (2024), p. 226 (page 4). [JST23] Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani. “List Decoding of Tanner and ...

    work page doi:10.1109/ccc.2008.28 2024

  3. [3]

    List Decodable Subspace Recovery

    arXiv: 1905.04660 . URL: https://doi.org/10.1137/1.9781611975994.10 (page 5). [RY20b] Prasad Raghavendra and Morris Yau. “List Decodable Subspace Recovery”. In: Proceedings of the 33rd Conference on Learning Theory (COLT 2020) . 2020, pp. 3206–3226. arXiv: 2002.03004. URL: https://proceedings.mlr.press/v125/ raghavendra20a.html (page 5). [Sar06] Tamás Sar...

    work page doi:10.1137/1.9781611975994.10 1905

  4. [4]

    Subspace Embeddings and ℓp-Regression Using Exponential Random Variables

    DOI: 10.1145/3564246.3585100. URL: https://doi.org/10.1145/3564246. 3585100 (pages 1, 2). [WZ13] David Woodruff and Qin Zhang. “Subspace Embeddings and ℓp-Regression Using Exponential Random Variables”. In: Proceedings of the 26th Annual Confer- ence on Learning Theory (COLT 2013). Vol. 30. Proceedings of Machine Learning Research. PMLR, 2013, pp. 546–567...

    work page doi:10.1145/3564246.3585100 2013