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
    Commented 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$ Commented 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$ Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .