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

AIPR assessment

This is a hard, competitive theory area, low-rank approximation and matrix norm approximation have active prior work and nontrivial barriers, so showing a PTAS for p > 2 and new p to q additive guarantees is a meaningful step. The strengths reinforce each other: a new proof viewpoint, a new rounding mechanism, and two problem families solved with the same template. The main weaknesses are not correctness red flags but practical ones, the methods are heavy, the notation is dense, and the runtime

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

Score Breakdown

More from this week

• Agentic World Modeling: Foundations, Capabilities, Laws, and Beyond
• How Hard is it to Decide if a Fact is Relevant to a Query?
• Railway Artificial Intelligence Learning Benchmark (RAIL-BENCH): A Benchmark Suite for Perception in the Railway Domain
• On first-order model checking parameterized by the number of variables
• Cuts and Gauges for Submodular Width

More in Optimization

• Optimal Online Equitable Allocation with Indivisible Resources