## Notes of Venkatesan Guruswami’s talk, jan. 21

By Passing UGC:

Inapproximability of subspace approximation

Scribes: Pierre Pansu and Jian Ding

Joint work with Prasad Raghavendra, Rishi Saket and Ji Wu, [GRSW].

There will be unconditional tight hardness results today. They were initially proved assuming UGC.

1. The problem and background

Definition 1 Subspace approximation.

Input: ${p\geq 2}$, ${m}$ points ${a_1 ,\ldots,a_m}$ in Euclidean ${{\mathbb R}^{n}}$. Output: a ${k}$-dimensional linear subspace ${H}$. Objective: Minimize

$\displaystyle \begin{array}{rcl} \sum_{i=1}^m d(a_i ,H)^p . \end{array}$

Special cases.

• ${p=2}$: Low rank matrix approximation; solvable in polynomial time by Singular Value Decomposition.
• ${p=\infty}$ and ${k=0}$: radii of point sets.

Previous results: Algorithmic

• Polynomial time approximation scheme for ${k=O(1)}$ and arbitrary ${p}$. [Feldman-monemizadeh-Sohler-Woodruff’10], [HarPeled-Varadarajan’02] [Shyamalkumar-Varadarajan’07], [Deshpande-Varadarajan’07].
• ${p = \infty}$ and arbitrary ${k}$: Ratio ${O(\sqrt{\log m})}$ approximation. [Varadarajan-Venkatesan-Ye-Zhang’07].
• For ${2: let ${\beta_p = \mathop{\mathbb E}_{g\sim N(0, 1)} |g|^p}$. [Deshpande-Tulsiani-Vishnoi’11] show ${2^{p/2}\beta_p}$-approximation for any ${k}$ and ${\beta_p}$-approximation for ${k=n-1}$.

Previous results: Hardness

• ${p=\infty}$: NP-hard [Brieden-Gritzman-Klee’00]; inapproximable within ${(\log m)^{\Omega(1)}}$ [Varadarajan-Venkatesan-Ye-Zhang’07].
• ${2, ${(\beta_p-\epsilon)}$-approximation is UGC hard (even for ${k=n-1}$). [Deshpande-Tulsiani-Vishnoi’11].

Note that ${\beta_p}$ is the ${p}$-th moment of a Gaussian, i.e.,

$\displaystyle \begin{array}{rcl} \beta_p &=&\mathop{\mathbb E}(|g|^p),\quad g\textrm{ standard Gaussian}\\ &=&\frac{2^{p/2}\Gamma(\frac{p+1}{2})}{\sqrt{n}}. \end{array}$

Definition 2 ${\ell_{p}}$-Grothendieck problem.

Input: An ${n\times n}$ matrix with diagonal entries ${0}$.

Output: A vector ${x\in\ell_p^n}$ with ${\|x\|_{\ell_p} \leq 1}$.

Objective: Maximize ${x^{\top}Ax}$.

• ${p=2}$: easy, largest singular value.
• ${p=\infty}$, “usual” Grothendieck problem. Admits ${O(\log n)}$-approximation. [Nesetrov’98, Megretski’99, Charikar-Wirth’04,…]. NP-hard to approximate within ${(\log n)^{\Omega(1)}}$. [Arora-Berger-Hazan-Kindler-Safra’05].
• ${2: [Kindler-Naor-Schechtman’08] proved ${(\beta_p^{2/p} - \epsilon)}$-inapproximability assuming UGC conjecture, and a nearly matching algorithm.

This talk: NP-hard to achieve an approximation ${< \beta_p^{2/p}}$, as well as a ${\beta_p^{2/p}}$ approximation algorithm (also in [Naro-Schechtman], unpublished).

2. Proofs

Use reduction from LABEL COVER (aka MAX PROJECTION).

The gadget is a dictatorship test. Remember one wants to find a unit vector ${b}$ minimizing

$\displaystyle \begin{array}{rcl} \sum|b\cdot a_i|^p . \end{array}$

Consider ${T = \{-1, 1\}^s}$. If ${b = e_i}$ for ${i\in [s]}$, we see ${\mathop{\mathbb E}_{x\in T} \langle b, x\rangle^p = 1}$. If ${\max_i |b_i| \leq \tau}$ for some small ${\tau = \tau(\delta)>0}$, then ${\mathop{\mathbb E}_{x\in T} \langle b, x\rangle^p \geq \beta_p - \delta}$. In order to see this, note that ${b\cdot x}$ converges in law to a standard Gaussian by Central Limit Theorem, for a random element ${x\in T}$. A quantitative bound is

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(|b\cdot x|\geq u)&\geq&\mathop{\mathbb P}(|g|\geq u)-2 \sum |b_i|^{3}\\ &\geq&\mathop{\mathbb P}(|g|\geq u)-\tau \,.\end{array}$

It follows that

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}(|b\cdot x|^p)\geq \beta_p (1-4\tau(\log(1/\tau)^{p/2})\sim\beta_p (1-\sqrt{\tau}). \end{array}$

Thus there is a ${\beta_p}$-gap between dictators and functions with low influences on ${T}$.

2.2. Reference hardness result

We want to plug this gadget into ${\alpha}$-smooth ${d}$ to ${1}$ expanding MAX PROJECTION. Precisely, consider ${(G = (V, E), s, r, \{\pi_{e, u} : e\in E, u \mbox{ incidents } e\})}$ such that

• ${\pi_{e, u} : [s] \mapsto [r]}$ with ${\pi^{-1}(e, u)(i) \leq d}$ for all ${e, u , i}$. (${d}$-to-${1}$)
• For all ${u\in V}$, ${i\neq j \in [s]}$, we have ${\mathop{\mathbb P}_{u\in e}(\pi_{e, u}(i)=\pi_{e, u}(j))\leq\alpha}$. (${\alpha}$-smoothness)
• For all ${W\subseteq V}$ and ${|W| = \gamma |V|}$, we have ${E(W) \geq \Omega(\gamma^2) |E|}$. (expansion)

Theorem 3 There exists ${C>0}$ such that ${(1,c^q)}$-approximation for ${4^q}$-to-${1}$ and ${100^{-q}}$-smooth expanding MAX PROJECTION is NP-hard for all ${q}$.

This is PCP + Parallel Repetition + a trick due to Khot. The key assumptions are that ${\alpha d\ll 1}$ and soundness ${c^q}$ tends to zero. Expansion comes for free.

Let ${n=|V|}$. For ${v\in V}$, let

$\displaystyle \begin{array}{rcl} X_v =\{x\in{\mathbb R}^{ns}\,:\,x(u,i)=0 \mbox{ for } u\neq v, \mbox{ and } x(v, i) \in \{1, -1\}\}\,. \end{array}$

Write ${X = \cup_v X_v}$. Consider

$\displaystyle \min \mathop{\mathbb E}_{x\in X} |\langle b, x\rangle|^p, \mbox{ subject to } \mathop{\mathbb E}_v \|b_v\|^2 = 1\,.$

If the value is less than ${\beta_v(1-\delta)}$, there exists about ${\delta}$-fraction of ${v\in V}$ such that ${b_v}$ has a coordinate ${i}$ with ${|b(v, i)| > \tau \|b_v\|}$.

Would like

$\displaystyle \sum_{j\in \pi_{e, u}^{-1}(i)} b(u, j) = \sum_{j\in \pi_{e, v}^{-1}(i)}(v, j)$

for all ${e = (u, v)}$, ${i\in [r]}$. For any edge ${e = (u, v)}$ and element ${j}$, define the vector ${h_{e,j}}$ as follows,

$\displaystyle h_{e,j} (w, i) = \begin{cases} 1, & \mbox{ if } w = u \mbox{ and } i \in \pi_{e, u}^{-1}( j)\\ -1, &\mbox{ if }w = u \mbox{ and } i\in \pi_{e,v}^{-1}(j)\\ 0, &\mbox{ otherwise.} \end{cases}\,.$

Take ${H = \mathrm{Span}_{e, j}(h_{e, j})}$ and let ${F = H^{\perp}}$. Now

$\displaystyle \min \mathop{\mathbb E}_v\mathop{\mathbb E}_{x\in \{\pm1\}^{ns}} |\langle b_v, x\rangle|^p$

subject to ${\mathop{\mathbb E}_v \|b\|^2 = 1}$ and ${b\in H^{\perp}}$.

2.4. Analysis

Completeness: Take ${b(v,i)=1_{\ell(u)=i}}$. It has value ${1}$ since it is a dictator in each vertex.

Soundness: List-decode small sets of labels for ${\sim \delta}$ fraction of vertices. Argue some sort of consistency.

Definition: Say ${v}$ is ${\tau}$-irregular if

$\displaystyle \begin{array}{rcl} \exists i \textrm{ such that } |b(v,i)|\leq\tau \|b_v\|. \end{array}$

Let ${\theta}$ be the fraction of ${\tau}$-irregular vertices. We already know that if ${v}$ is ${\tau}$-regular,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}(|b\cdot v|^p)\geq \beta_p (1-\sqrt{\tau})\|b_v\|_{2}^{p} \end{array}$

So for ${\tau=\delta^{10}}$, there exists ${\theta(\delta,p)}$ such that ${\theta}$-fractions of vertices are ${\tau}$-irregular. So we need only worry on such vertices. For such a vertex ${v}$, define

$\displaystyle \begin{array}{rcl} \Gamma_v =\{i\,;\, |b(v,i)|>\tau \|b_v\|\} \end{array}$

By construction, it is non empty and of size ${<\tau^{-2}}$. We prove that for edges ${e=uv}$, ${\pi_{e,u}(\Gamma_u)}$ and ${\pi_{e,v}(\Gamma_v)}$ intersect. By ${\alpha}$-smoothness, the probability that this occurs is small.

Naor: Is the ${(n-1)}$-subspace problem a special case of the Grothendieck problem ? Answer: essentially yes.