4
$\begingroup$

I am able to show that any $k$-dimensional subspace of $\mathbf{R}^{Ck\log(k)}$ must contain a unit vector $x$ such that $\|x\|_{\infty} \ge c\sqrt{1/\log(k)}$ for a small enough constant $c$.

But is there a $k$-dimensional subspace of $\mathbf{R}^{Ck\log(k)}$ such that every nonzero vector $x$ in the subspace satisfies $\|x\|_{\infty} \ge (1/\text{poly}(\log(k)))\|x\|_2$? And is there any random rotation that can be applied to a given $k$-dimensional subspace such that the subspace obtained after rotating has this property with some constant probability?

$\endgroup$
3
  • $\begingroup$ can you show how you prove the claim in the first sentence $\endgroup$
    – kodlu
    Jun 26, 2021 at 12:22
  • 1
    $\begingroup$ @kodlu Consider an orthonormal basis, represented by a matrix $U$, for a $k$-dimensional subspace of $\mathbb{R}^{Ck\log(k)}$. As $U$ has $Ck\log(k)$ rows and $\|U\|_F^2 = k$, there must exist a row of $U$, say $U_{i}$ with $\|U_i\|_2 \ge \sqrt{k/Ck\log(k)}$. So, $U \cdot (U_i^T)/\|{U_i^T}\|$ which is a unit vector in the subspace has a coordinate of value $\|U_i\|_2 \ge \sqrt{k/Ck\log(k)} = \sqrt{1/C\log(k)}$. $\endgroup$ Jun 26, 2021 at 17:25
  • $\begingroup$ You can consider the set of vector that are all supported on a small set of coordinates (the same set for all vectors). If they are supported on $m$ coordaintes then every $x$ will satisfy $\|x\|_{\infty} \ge 1/\sqrt{m}$ which is large if $m$ is sufficiently small (not sure how interesting this example is). Its also probably not the case that a random rotation will get you close to one of these subspaces but also not sure. $\endgroup$ Jul 3, 2021 at 21:44

1 Answer 1

4
$\begingroup$

Since this hasn't been answered, I think the answer is no.

Indeed, suppose that there exists a $k$-dimensional subspace $V$ of $\mathbb{R}^n$ such that for all $\mathbf{x}\in V$, \begin{equation} \frac{\|\mathbf{x}\|_2}{D}\leq \|\mathbf{x}\|_{\infty}\leq \|\mathbf{x}\|_2, \end{equation} for some value of $D\geq 1$. Equivalently, there exists a linear transformation $T:\mathbb{R}^k\to \mathbb{R}^n$ that maps onto $V$ and preserves the $2$-norm (namely, let the columns be an orthonormal basis of $V$), so that this is equivalent to \begin{equation} \frac{\|\mathbf{x}\|_2}{D}\leq \|T\mathbf{x}\|_{\infty}\leq \|\mathbf{x}\|_2 \quad\forall \mathbf{x}\in \mathbb{R}^k. \end{equation} By considering the rows of $T$, this means there exists $n$ vectors $\mathbf{t}_1,\ldots,\mathbf{t}_n\in \mathbb{R}^k$ with at most unit length such that for any vector $\mathbf{x}\in S^{k-1}$, \begin{equation} \max_{i\in [n]} \vert \langle \mathbf{t}_i,\mathbf{x}\rangle\vert\geq \frac{1}{D}. \end{equation}

Consider a random vector $\mathbf{X}$ drawn uniformly from $S^{k-1}$. The distribution of $\vert \langle \mathbf{t}_i/\|\mathbf{t}_i\|_2,\mathbf{X}\rangle\vert$ does not depend on $\mathbf{t}_i$, and by concentration of measure on the sphere, the probability that $\vert \langle \mathbf{t}_i,\mathbf{X}\rangle\vert$ exceeds $O\left(\sqrt{\frac{\log n}{k}}\right)$ is less than $1/n$ (as $\|\mathbf{t}_i\|_2\leq 1$). If $D\leq c\sqrt{\frac{k}{\log n}}$ for some sufficiently small constant $c$, we obtain a contradiction as there exists a vector violating the desired inequality. Therefore, $k\leq CD^2\log n$ for some large enough constant $C$. For your regime of $D=\text{polylog}(n)$, this unfortunately implies a polylogarithmic upper bound on the dimension of $k$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.