The motivation for this question comes from [this paper](http://www.sciencedirect.com/science/article/pii/S0885064X14000831/) 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.



A lower bound on $\|\cdot\|_{p_{\ast}}$ image of $\ell^{q_{\ast}}$ vectors
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}$. 


