3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice paper Cristóbal! I should read it! $\endgroup$
    – Suvrit
    Oct 17, 2014 at 21:45
  • $\begingroup$ Thank you, Suvrit. I hope it is up to your expectations. $\endgroup$ Oct 18, 2014 at 3:34

2 Answers 2

4
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ This is really neat! Thank you, Professor. $\endgroup$ Oct 22, 2014 at 20:55
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer, Professor Johnson. You correctly understood the question. Unfortunately, the interesting case is indeed when $q_{\ast}>p_{\ast}$. If it makes life any easier, the case $q=2<p\leq \infty$ is already very interesting to me. $\endgroup$ Oct 18, 2014 at 3:23
  • 1
    $\begingroup$ OK. The problem looks interesting. What relationship between T and n is interesting for you? For fixed T, when $p\not= q$, it is clear that your parameter tends to infinity as $n\to \infty$ (a lower bound is $C n^{1/p_* - 1/q_*}/T^{1/2}$). Here I assume that $n \ge 2T$ when $q\not =2$. $\endgroup$ Oct 18, 2014 at 16:43
  • $\begingroup$ A lower bound for $T\leq cn$, where $0<c<1$ is interesting. How do you get that lower bound? and is there an issue when $q=2$? $\endgroup$ Oct 18, 2014 at 17:19
  • $\begingroup$ BTW, I am a bit surprised by the expression: I was expecting something like $Cn^{1/p_{\ast}-1/{q_{\ast}}}/T^{1/q_{\ast}}$, but I might incorrectly extrapolated the bounds. $\endgroup$ Oct 18, 2014 at 22:33
  • 1
    $\begingroup$ I have been traveling internationally to a conference the last couple of days and haven't had time to think about this or write anything down. Manana (which I think translates into English as "some indeterminate time in the future"). :) $\endgroup$ Oct 19, 2014 at 20:03

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.