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

<p>$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$</p>

<p>for some small $\epsilon &gt;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 <b>explicit construction</b> of such spaces.</p>

<p>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.</p>

<blockquote>
  <p>What is the complexity of this problem? Are hardness of approximation results known?</p>
</blockquote>

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

CC BY-SA 2.5
2011-02-19T16:14:01.110Z
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
CC BY-SA 2.5
2011-02-19T19:50:59.927Z
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
CC BY-SA 2.5
2011-03-28T21:32:34.573Z
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](http://arxiv.org/abs/1103.4984) on checking whether a matrix satisfies the restricted isoperimetry property (RIP) and related problems.
arnab
<cc.complexity-theory><cg.comp-geom><norms><compressed-sensing>
complexity of checking if a subspace is a Euclidean section of L1
Luca Trevisan
# complexity of checking if a subspace is a Euclidean section of L1

(Asked by: username_0 on 2011-02-18)

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?

**Tags:** cc.complexity-theory, cg.comp-geom, norms, compressed-sensing
> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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$.)  
> **username_2**: 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](http://arxiv.org/abs/1103.4984) on checking whether a matrix satisfies the restricted isoperimetry property (RIP) and related problems.  

---

## 0 answers

