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