AI summaryⓘ
The authors study a problem where you want to find a simple (low-rank) matrix close to a given matrix by measuring how close they are entry by entry using a certain kind of math distance called the p norm. While solving this is easy when p equals 2, they focus on the harder cases where p is an even number greater than 2. The authors provide the first efficient algorithm that gets very close to the best possible solution for these cases. They do this by using advanced mathematical tools called convex hierarchies instead of older methods that dont work well here. They also apply their approach to related problems in matrix norms, offering new approximation algorithms for challenging parameter ranges.
entrywise low-rank approximationl_p normsingular value decompositionSherali-Adams hierarchyconvex optimizationpolynomial-time approximation scheme (PTAS)matrix p 19 q normssmall-set expansionquantum informationadditive approximation
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$.