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<p<\infty}: 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<p<\infty}, {(\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<p<\infty}: [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).

2.1. The gadget

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.

2.3. Plugging in the gadget

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.


[GRSW] Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Ji; Bypassing UGC from some optimal geometric inapproximability results. ECCC Technical Report TR10-177


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s