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: , points in Euclidean . Output: a -dimensional linear subspace . Objective: Minimize
- : Low rank matrix approximation; solvable in polynomial time by Singular Value Decomposition.
- and : radii of point sets.
Previous results: Algorithmic
- Polynomial time approximation scheme for and arbitrary . [Feldman-monemizadeh-Sohler-Woodruff’10], [HarPeled-Varadarajan’02] [Shyamalkumar-Varadarajan’07], [Deshpande-Varadarajan’07].
- and arbitrary : Ratio approximation. [Varadarajan-Venkatesan-Ye-Zhang’07].
- For : let . [Deshpande-Tulsiani-Vishnoi’11] show -approximation for any and -approximation for .
Previous results: Hardness
- : NP-hard [Brieden-Gritzman-Klee’00]; inapproximable within [Varadarajan-Venkatesan-Ye-Zhang’07].
- , -approximation is UGC hard (even for ). [Deshpande-Tulsiani-Vishnoi’11].
Note that is the -th moment of a Gaussian, i.e.,
Definition 2 -Grothendieck problem.
Input: An matrix with diagonal entries .
Output: A vector with .
Objective: Maximize .
- : easy, largest singular value.
- , “usual” Grothendieck problem. Admits -approximation. [Nesetrov’98, Megretski’99, Charikar-Wirth’04,…]. NP-hard to approximate within . [Arora-Berger-Hazan-Kindler-Safra’05].
- : [Kindler-Naor-Schechtman’08] proved -inapproximability assuming UGC conjecture, and a nearly matching algorithm.
This talk: NP-hard to achieve an approximation , as well as a approximation algorithm (also in [Naro-Schechtman], unpublished).
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 minimizing
Consider . If for , we see . If for some small , then . In order to see this, note that converges in law to a standard Gaussian by Central Limit Theorem, for a random element . A quantitative bound is
It follows that
Thus there is a -gap between dictators and functions with low influences on .
2.2. Reference hardness result
We want to plug this gadget into -smooth to expanding MAX PROJECTION. Precisely, consider such that
- with for all . (-to-)
- For all , , we have . (-smoothness)
- For all and , we have . (expansion)
Theorem 3 There exists such that -approximation for -to- and -smooth expanding MAX PROJECTION is NP-hard for all .
This is PCP + Parallel Repetition + a trick due to Khot. The key assumptions are that and soundness tends to zero. Expansion comes for free.
2.3. Plugging in the gadget
Let . For , let
Write . Consider
If the value is less than , there exists about -fraction of such that has a coordinate with .
for all , . For any edge and element , define the vector as follows,
Take and let . Now
subject to and .
Completeness: Take . It has value since it is a dictator in each vertex.
Soundness: List-decode small sets of labels for fraction of vertices. Argue some sort of consistency.
Definition: Say is -irregular if
Let be the fraction of -irregular vertices. We already know that if is -regular,
So for , there exists such that -fractions of vertices are -irregular. So we need only worry on such vertices. For such a vertex , define
By construction, it is non empty and of size . We prove that for edges , and intersect. By -smoothness, the probability that this occurs is small.
Naor: Is the -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