| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

13. Finding Subsets of Vectors with Large Average Correlation


    1. Add remark

      Problem 13.1.

      [Alex Andoni] For $\varepsilon,\delta>0$ and unit vectors $v_1,v_2,\ldots,v_n\in \ell_2$, consider the following two properties:
      1. (a) $\langle v_i, v_j\rangle \le 2\varepsilon$ whenever $i\neq j$, and
      2. (b) for each $i$, there exists $A_i\subseteq \{1,2,\ldots,n\}$ such that $|A_i|\ge n^{1-\delta}$ and $\langle v_i, v_j\rangle \ge \varepsilon$ for all $j\in A_i$.
      What is the largest $\delta$, in terms of $\varepsilon$, such that for any unit vectors $v_1,v_2,\ldots,v_n\in \ell_2$ satisfying (a) and (b), there exists $I\subseteq \{1,2,\ldots,n\}$ with \[ |I|\ge n^{1-O(\delta)} \qquad\text{and}\qquad \frac{1}{|I|^2}\sum_{i,j\in I}\langle v_i, v_j\rangle = \Omega(\varepsilon)\, ? \]

          Cite this as: AimPL: Metric embeddings, available at http://aimpl.org/metricembeddings.