A lower bound on $\|\cdot\|_{p_{\ast}}$ image of $\ell^{q_{\ast}}$ vectors

Question

The motivation for this question comes from this paper where we study lower bounds on the complexity of convex optimization algorithms (BTW, if you find a better title for my question, please let me know).

Some notation: let $X=B_p^n$ be the unit ball of $(\mathbb{R}^n,\|\cdot\|_p)$, and let $Y=B_{q_{\ast}}^n$ be the unit ball of $(\mathbb{R}^n,\|\cdot\|_{q_{\ast}})$, where $2\leq p,q \leq \infty$ and $1/q+1/q_{\ast}=1$ (in the paper we consider the case $p=q$).

Let now $T\leq n$. One of the key ingredients of our analysis depends on finding linear functionals $\xi^t\in Y$, $t=1,\ldots,T$, such that we can lower bound, for arbitrary $s_t=\pm 1$, the quantity $$ \Delta_{p,q}^{T,n} = -\min_{x\in X} \max_{1\leq t\leq T} s_t \langle \xi^t,x\rangle. $$ In the case $p=q$ this is done by simply picking $\xi^t$ to be the first $T$ canonical vectors, which gives $\Delta_{p,p}^{T,n}\geq 1/T^{1/p}$. My question is whether there exist good lower bounds when $p\neq q$.

In general, by simple dualization arguments, this turns out to be equivalent to $$ \Delta_{p,q}^{T,n} = \min_{\lambda \in \partial B_1^T} \left\|\sum_{t=1}^T \lambda_t \xi^t \right\|_{p_{\ast}}, $$ where $\partial B_1^T$ denotes the boundary of the $\|\cdot\|_1$-unit ball. Therefore, we are just looking for a linear transformation $\Xi:B_1^T\to B_{p_{\ast}}^n$ (in matrix form: $\Xi=[\xi^1|\ldots|\xi^T]$, where each $\|\xi^t\|_{q_{\ast}}=1$) with $\mbox{ker}(\Xi)=0$, and with the image of the boundary of the cross-polytope as far as possible from the origin.

This question looks remarkably similar to some computations for $\ell_p$ embeddings in the local theory of Banach spaces. However, this is far from my expertise, so I haven't been able to extract useful ideas from there.

If you see some explicit connection with something that is known (or figure out a simple way to lower bound $\Delta$), please let me know.

Answer 1

Not being able to sleep due to jet lag, I had a chance to think about your problem a bit. The answer is elementary and simple, but I will say more than is necessary.

First, people interested in quantitative information about $\ell^n_p$ have learned that it is usually better to to work with $L_p^n$ rather than $\ell^n_p$. This simplifies formulas and sometimes even suggests better ways to view problems. Denote the $L_p^n$ norm by $|\cdot|_p$, so $\|\cdot \|_p = n^{1/p}|\cdot |_p$. So we are viewing $L_p^n$ as being $L_p(\mu_n)$, where $\mu_n$ is the uniform probability measure on $\{1,\dots,n\}$, and the $|\cdot |_p$ norms are increasing functions of $p$. Also, since you are interested in norms on the left side of $2$, I will use $p$ (respectively, $q$) for your $p_*$ (respectively, $q_*$) and use a $*$ superscript rather than subscript for the dual norms.

With this normalization, the answer to your problem is essentially independent of $n$, and you can formulate a version of your problem for $L_p : = L_p(0,1)$. I’ll also denote the norm on $L_p$ by $|\cdot |_p$.
Coming back to $L_p^n$ from $L_p$ introduces a constant factor of at most $2$.

Problem: Fix a positive integer $T$ and let $1 \le p \le q \le 2$. Compute the sup over all norm one operators $S: \ell_1^T \to L_q$ of $$ \alpha_{p,q}(S) := \inf \{|Sx|_p : \|x\|_{\ell_1^T} = 1\}. $$

Denote this supremum by $\alpha_{p,q}$. So, as you (in effect) said at the beginning of your post, $\alpha_{q,q}=T^{-1/q^*}$. That for a norm one $S$ we have $\alpha_{q,q}(S) \le T^{-1/q^*}$ is immediate from the fact that $L_q$ has type $q$ with constant one (see e.g. the book of Albiac and Kalton). The other inequality comes from considering an operator $S$ that maps the unit vector basis for $\ell_1^T$ to disjoint norm one functions in $L_q$.

Since $| \cdot |_r$ is an increasing function of $r$, it is clear that $\alpha_{p,q} \le \alpha_{q,q} $ for $1\le p \le q \le 2$. It remains to show that $\alpha_{p,q} \ge T^{-1/q^*}$. To do this, take $T$ disjoint subsets $A_1,\dots,A_T$ of $(0,1)$ each having measure $T^{-1}$ and consider
$S:\ell_1^T \to L_q$ defined by $Se_j := T^{-1/q} 1_{A_j}$; $1 \le j \le T$.

Coming back to $L_p^n$, we cannot quite do that last step if $T$ does not divide $n$, but you can choose the $T$ disjoint subsets of $\{1,\dots,n\}$ so that each set has measure between $(2T)^{-1} $ and $T^{-1}$.

Answer 2

This is really a comment rather than an answer, but it is too long for a comment and I feel compelled to say something because you used my tag. :)

I do not understand the first statement of your problem, but I think that after some struggling I understand the dual statement that you say is equivalent. In the case that $2< p = q $ it says (I think)

Given $T \le n$, what is the minimum Banach-Mazur distance from $\ell_1^T$ into $\ell_{p_*}^n$? In other words, what is the minimum of $\|T^{-1}\|$ over all norm one operators $T$ from $\ell_1^T$ onto a subspace of $\ell_{p_*}^n$?

The answer to this question; namely, $T^{1-1/p_*} = T^{1/p}$ is, not surprisingly, well known to Banach space theorists (your post suggests that you know this). For others: it is an immediate consequence of the fact that $L_{p_*}$ has type $p$ with constant one (see e.g. the book of Albiac and Kalton).

Your question for general $2\le p,q$ asks (again, if I understand)

what is the minimum of $\|T^{-1}\|$ from $\ell_1^T$ onto a subspace of $\ell_{p_*}^n$, where the minimum is taken over all norm one operators from $\ell_1^T$ into $\ell_{q_*}^n$?

If $q_*\le p_*$, then clearly again the answer is $T^{1/p}$. I do not know whether this question has been considered when $q_* > p_*$. I'll think about it if my understanding of your question is correct.