# complexity of checking if a subspace is a Euclidean section of L1

If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have

$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$

for some small $\epsilon >0$, then we say that $X$ is an almost-Euclidean section of $\ell_1^n$, and (the matrix whose image is) X is useful in compressed sensing. A random subspace works excellently, and there is a huge research program devoted to the explicit construction of such spaces.

Is it known what is the complexity of approximating the "Euclidan-sectionness" of $X$? That is, given a subspace $X$, say presented via a basis, consider the problem of finding the unit (in $\ell_2$ norm) vector in $X$ of smallest $\ell_1$ norm.

What is the complexity of this problem? Are hardness of approximation results known?

Apart from specific applications, these seem to be interesting problems. Is it known what is the complexity of finding the vector of maximum $\ell_1$ norm among the unit vectors of a given subspace?

• The above inequality is slightly wrong. You probably mean that $(1-\varepsilon)||x||_1 /\sqrt{n} \leq ||x||_2 \leq ||x||_1/\sqrt{n}$. Indeed, for any $x$, $||x||_1 \geq ||x||_2$. – Sariel Har-Peled Feb 19 '11 at 16:14
• Thanks Sariel, I had inverted the places of $\ell_1$ and $\ell_2$. (If you want $\ell_2$ in the middle, then it should be $||x||_1/\sqrt n \leq ||x||_2 \leq (1+\epsilon)||x||_1 / \sqrt n$, because it's always $||x||_1 \leq \sqrt n ||x||_2$.) – Luca Trevisan Feb 19 '11 at 19:50
• This is not an answer to your question. But in the vein of computational problems arising from compressed sensing applications, Koiran and Zouzias have a recent paper on checking whether a matrix satisfies the restricted isoperimetry property (RIP) and related problems. – arnab Mar 28 '11 at 21:32