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?

  • 3
    $\begingroup$ 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$. $\endgroup$ Feb 19, 2011 at 16:14
  • 1
    $\begingroup$ 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$.) $\endgroup$ Feb 19, 2011 at 19:50
  • $\begingroup$ 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. $\endgroup$
    – arnab
    Mar 28, 2011 at 21:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.