Скачать или смотреть Ainesh Bakshi: "Additive Approximation Schemes for Low-Dimensional Embeddings"

In this talk, I will discuss algorithms for fitting low-dimensional embeddings to high-dimensional data. In particular, I will focus on the Euclidean Metric Violation problem (EMV), where the input is an arbitrary non-negative vector in $n^2$-dimensional space and the goal is to find the closest $k$-dimensional Euclidean metric on $n$ points to this input vector. This problem was shown to be NP-Hard by Dayton and Dasgupta in 2006, even when $k=1$. Dhamdhere gave a $log(n)$-approximation when $k=1$ in 2004, and left obtaining a PTAS as an open question. Independently, the same problem has been studied for over 70 years in the statistics community, where it goes by the name of multi-dimensional scaling, and there are no approximation algorithms known for any $k$ greater than $1$.

I will describe the first additive approximation scheme for EMV, which I believe is a crucial first step towards obtaining a PTAS. The key technical contribution of this work is a new analysis of correlation rounding for Sherali-Adams / Sum-of-Squares relaxations, tailored to low-dimensional embeddings. The techniques I describe are broadly applicable, and yield additive approximation schemes for weighted variants of EMV as well as entry-wise $L_p$ low-rank approximation.

Based on joint work with Prashanti Anderson and Sam Hopkins.