Tighter upper bounds with ratios of powers of norms

Question

This question concerns concentration or sparsity measures for finite sequences, related to ratios of norms and their powers. They are meant for approximations to the $\ell_0$ count index.

Their computation and properties have shown renewed interest in the framework of sparse signal restoration or high-dimensional data analysis. A reference is given at the bottom for some more context.

Given a vector $x\in \mathbb{R}^K$ and $1 \le r < s$, I would like to find a tight upper bound for the quantity: $$\psi_{r,s}(x) = \frac{\sum_1^K |x_k|^r}{1+\sum_1^K |x_k|^s}\,.$$ Using Hölder inequalities (see Inequalities in $l_p$ norm), one gets: $$\sum_1^K |x_k|^r \le K^{1-r/s} \left(\sum_1^K |x_k|^s \right)^{r/s}.$$ Function $u \mapsto \frac{u^r}{1+u^s}$ is upper bounded by the relatively symmetric expression: $$ \mu_{r,s} = \left(\frac{r^r (s-r)^{s-r}}{s^s} \right)^{1/s}$$ reached at $u_0 = \left(\frac{r}{s-r}\right)^{1/s}$ (which also works asymptotically when $ r= s$, with the $0^0 = 1$ convention).

Thus, $$\psi_{r,s}(x) \le K^{1-r/s}\mu_{r,s}\,.$$

For $r=1$ and $s=2$ with $K=2$, the graph of $\psi_{r,s}(x)$ is displayed below:

Here, the $\mu_{r,s}$ bound is reached. Yet numerically, with random vectors, I suspect that this bound is not tight in general. My questions are thus:

1. Are there tighter bounds, potentially using supplementary hypotheses :
   • based on $\max |x_k|$? I would prefer to allow $\min |x_k|=0$, since we are interested in sparse sequences, with a large proportion of zero or close to zero values.
   • based on decay laws: e.g. $|x_k|\propto k^{-\alpha}$, $\alpha>0$ for $k\le k_s$, and $x_k=0$ for $k> k_s$ for some $k_s< K$
2. Can one get estimates of spatial locations $x\in \mathbb{R}^K$ close to the maxima, or bounding areas?

For a little more practical context, see Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed l1/l2 Regularization.

Answer 1

Consider the closely related function $$Q_{r,s}(x)=\frac{\left(\sum_{k=1}^K x_k^r\right)^{1/r}}{\left(\sum_{k=1}^K x_k^s\right)^{1/s}}$$ which is the unweighted counterpart of a ratio defined in Mitrinovic's classic Analytic Inequalities, section 2.14.3, published by Springer many decades ago.

Assuming $0<m\leq x_k \leq M$ for all $k,$ and letting $C=M/m,$ Mitrinovic states the bound, $$ Q_{r,s}(x)\leq \left(\frac{r(C^s-C^r)}{(s-r)(C^r-1)} \right)^{1/s} \left( \frac{r(C^r-C^s)}{(r-s)(C^s-1)} \right)^{-1/r} $$ I am not sure if this will improve on your result, unless the plus one term in your denominator can be neglected, so that this function is close to your ratio, so very large $K$ might be a case where this bound is better.

It does, however, use both the maximum and the minimum. Some related results discussed in that section of the book refer to conditions for equality, which is a kind of concentration of the entries to $m$ and $M$, under some special conditions.

One other reference given with no details by Mitrinovic is Beckenbach, E. F., American Mathematical Monthly,71:606-619, 1964, where apparently the upper bound is also discussed.