{"id":"b7d8461e-f00a-4062-a943-036cf9eee51b","arxiv_id":"2604.22699","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A PTAS for entrywise low-rank approximation under even p>2 norms via Sherali-Adams rounding, plus additive approximations for p<22","rationale":"The reader's weakest assumption correctly flags the missing rounding details. After reading the full text the same spot remains the least secure: the paper must prove that global correlation rounding succeeds for a non-linear (degree-p) objective over a continuous domain, and the provided sketch does not make the moment-control argument explicit enough to rule out an Ω(1) loss. This is not a contradiction but a place where the PTAS guarantee could silently degrade; the concrete test above would settle it directly.","tokens_in":1823,"tokens_out":465,"duration_ms":59731,"concrete_test":"Extract the precise rounding theorem (e.g., Theorem 4.3 or 5.1) and the moment degree d used; instantiate a 2×2 rank-1 instance where A has entries of magnitude 10 and the optimal B is known; solve the SA relaxation at the claimed degree, apply the rounding procedure, and check whether the output p-norm is within (1+ε) of the hierarchy value for ε=0.1 and p=4.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires that a constant-degree Sherali-Adams solution (degree depending only on k, p, ε) can be rounded via global correlation rounding to a rank-k matrix B whose entrywise p-norm is (1+ε)-close to the hierarchy value, which itself is (1+ε)-close to OPT. For even p the objective is a degree-p polynomial in the matrix entries. The rounding step (presumably in §4 or §5) must therefore show that the pseudo-expectation of the p-norm is preserved up to (1+ε) after rounding; this typically needs moment bounds or correlation decay that the hierarchy level may not guarantee once the variables are the (unbounded) entries of a rank-k factorization. If the analysis only controls pairwise correlations and treats the p-norm via crude bounds, the additive error can become Ω(1) rather than ε·OPT when the matrix has large entries.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.3","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<22 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":[{"comment":"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.","section":null},{"comment":"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.","section":null}],"minor_comments":[{"comment":"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.","section":null}],"recommendation":"major_revision","confidential_remarks":"The manuscript positions itself as establishing a 'blueprint' for hierarchies in continuous optimization; the editor may wish to verify that the novelty disclosure relative to prior SA applications (e.g., in combinatorial optimization) is accurate."},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"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."},{"response":"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_made":"yes","referee_comment":"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."}],"tokens_in":1573,"tokens_out":718,"duration_ms":69274,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that they get a PTAS for finding the best rank-k matrix B minimizing the entrywise p-norm distance to A, when p is even and greater than 2. This improves on the prior 3+eps factor, bi-criteria results, and additive schemes, and they extend the same method to give nontrivial additive approximations for matrix p to q norms in the mixed regime p<22) to lifting the problem into the Sherali-Adams hierarchy and rounding via global correlation methods. That template for applying hierarchies to continuous non-convex objectives is the part that could travel to other problems. The claims line up with what the abstract states, and the improvements over the three cited prior works are concrete. The soft spot sits in the rounding step. The p-norm objective is a degree-p polynomial, so preserving a (1+eps) guarantee after rounding requires that the pseudo-distribution controls the relevant higher moments or correlations induced by the absolute values. If the analysis only gets pairwise control and then applies crude bounds, the error can pick up additive terms that ruin the PTAS when entries are large. The paper presumably closes this with a degree that depends only on k, p, and eps, but that is the section I would read first to confirm the constants work out. This is for people working on approximation algorithms for matrix problems or on convex hierarchies for optimization. A reader who follows either area would get usable techniques and a new result to build on. It deserves a serious referee because the claims are strong enough and the method is not just incremental.","headline":"This paper gives the first PTAS for entrywise low-rank approximation under even p>2 norms via Sherali-Adams plus global correlation rounding, plus new additive approximations for p-q matrix norms.","tokens_in":2501,"tokens_out":417,"would_cite":true,"duration_ms":20786,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"For even p > 2 and fixed rank k, a convex hierarchy yields a polynomial-time approximation scheme for entrywise low-rank matrix approximation.","keywords":["entrywise low-rank approximation","matrix norms","Sherali-Adams hierarchy","global correlation rounding","polynomial time approximation scheme","convex relaxation","continuous optimization","p to q norms"],"falsifier":"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 ε.","tokens_in":2725,"feed_emoji":"","tokens_out":759,"duration_ms":26023,"temperature":0.7,"pith_summary":"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.","feed_headline":"Convex hierarchy delivers first PTAS for entrywise low-rank approximation","feed_subtitle":"For even p>2 and fixed rank k the method approximates the best low-rank matrix in entrywise p-norm to arbitrary precision.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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<22","Global correlation rounding PTAS for entrywise low-rank approx","PTAS for p-norm entrywise low-rank using Sherali-Adams hierarchy","Additive approximations for p-q matrix norms with p<22","Global correlation rounding PTAS for entrywise low-rank approx","PTAS for p-norm entrywise low-rank using Sherali-Adams hierarchy","Additive approximations for p-q matrix norms with p<22 where no rank-k matrix from the rounded hierarchy solution achieves error within 1+ε of the true minimum, for small enough ε.","supporting_citations":[],"review_version":1}