1
$\begingroup$

Informally, I want to ask if two functions $f$ and $g$ on the Hamming cube have the same Fourier spectra but w.r.t different measure and basis, then is $||f||_p$ related to $||g||_p$? (Where each $p$-norm is measured according to the appropriate measure.) This question requires some notation to set up more precisely.

First, for the Hamming cube $\{0,1 \}^d$, given a bias parameter $0 \leq b \leq 1$, we may construct a biased measure $\mu_b$ that assigns a weight $b$ to $1$ bits and $1-b$ to $0$ bits as follows:

\begin{equation} \mu_b(x) = b^{\sum_i x_i} (1-b)^{d - \sum_i x_i}. \end{equation}

We continue that expectations and $l_p$-norms can also be defined under this measure. So for example, $ E_b[f] = \sum_{x \in \{0,1\}^d} \mu_b(x) f(x)$ and $||f||_p = \left( \sum_{x \in \{0,1 \}^d} \mu_b(x) (f(x))^p \right)^{\frac{1}{p}} $. We note now an Fourier parity basis for the space $F_b$ of all functions $f: \{0,1\}^d \to \mathbb{R}$ when $\{0,1\}^d$ is associated with measure $\mu_b$. First for each $x \in \{0,1\}^d$ and $i \in [d]$ we define: \begin{equation}\chi_i^b = \begin{cases} \sqrt{\frac{b}{1-b}} & x_i = 0 \\ -\sqrt{\frac{1-b}{b}} & x_i = 1 \\ \end{cases} \end{equation}

This set of $\chi_i^b$ essentially correspond to a bit wise parity basis, which we can extent to arbitrary $S \subset [d]$ as $\chi_S^b(x) = \prod_{i \in S} \chi_i^b(x)$. The collection $\{\chi_S^b \}$ over all $S \subset [d]$ is now our desired orthonormal basis of size $2^d$. All this notation reduces to the standard Fourier basis and notions for $b = \frac{1}{2}$.

Now after all that lengthy build-in, here is my question. Suppose $f$ is a function over $\{0,1 \}^d$ with measure $\mu_{1/2}$ and $g$ is a function over $\{0,1 \}^d$ with measure $\mu_b$ (for $b \neq \frac{1}{2}$) and suppose $f$ and $g$ have the same Fourier cofficients w.r.t their corresponding bases elements $\chi_S^{1/2}$ and $\chi_S^b$ . Parseval's immediately implies $||f||_2 = ||g||_2$, where each norm is calculated according to the measure of the space the function lies in ($\mu_{1/2}$ and $\mu_b$ respectively). Is this true for all the $l_p$ norms on the Hamming cube? And if not, as I believe to be the case, is there at least some general relation between $||f||_p$ and $||g||_p$?

(Note:This question is crossposted from CS theory stackexchange , where there has been no answer for two weeks.)

$\endgroup$
2
  • $\begingroup$ Link to TCS version. Also, I think in "$\mu_b$ assigns a weight $b$ to $0$ bits and $1−b$ to $1$ bits" you have 0 and 1 switched around. (Looking at the definition of $\mu_b$ that immediately follows.) $\endgroup$ Dec 25, 2013 at 4:24
  • $\begingroup$ Also, you sometimes write $[n]$ instead of $[d]$. $\endgroup$ Dec 25, 2013 at 4:58

1 Answer 1

1
$\begingroup$

You are right, $l_p$ norms need not the same for $p\ne 2$. Take $d=1$, $f=\chi^{1/2}_1$ and $g=\chi^b_1$: then $\|f\|_p=1$ for all $p$, but for $b\ne 1/2$,
$$\|g\|_p=\left(\left(\frac{b}{1-b}\right)^{p/2}(1-b)+\left(\frac{1-b}{b}\right)^{p/2}b\right)^{1/p} \tag{1}$$ which is a strictly increasing function of $p$. As $p\to\infty$, (1) grows to $$\left(\max\left(\frac{b}{1-b},\frac{1-b}{b}\right)\right)^{1/2} $$

On the other hand, for $f=g\equiv 1$ we have $\|f\|_p=\|g\|_p=1$ for all $p$. This shows that there is no direct relation (in the form of an identity) between the $l_p$ norms in two different measures.

One can write down some inequalities, of course. The crudest one is obtained just by using the fact that $\|f\|_2=\|g\|_2$ and the general relation between $\ell_p$ norms on purely atomic probability spaces. Namely, if $\delta$ is the smallest measure of an atom, then $p\mapsto \delta^{-1/p}\|f\|_p$ is a decreasing function of $p$, while $\|f\|_p$ is an increasing function of $p$. For unbiased measure we have $\delta=2^{-d}$, hence
$$ 2^{d/2-d/p}\le \|f\|_p \le 1,\quad 1\le p\le 2 $$ $$ 1 \le \|f\|_p \le 2^{d/2-d/p},\quad 2\le p\le \infty $$ For the biased measure (i.e., for $g$) similar estimates hold with $2$ replaced by $1/\min(b,1-b)$. This allows you to compare $\|f\|_p$ and $\|g\|_p$ by chaining the inequalities above. As I said, this is crude in the sense that the information about coefficients is used only through Parseval.

You can certainly do better, but I'm afraid you can't do spectacularly better than that. Take $f=\chi^{1/2}_S$ and $g=\chi^b_S$ where $S=[d]$. The maximum of $g$ is $$\left(\max\left(\frac{b}{1-b},\frac{1-b}{b}\right)\right)^{d/2} \tag{2}$$ which is pretty big compared to $1$. And when $p$ is large, the $l_p$ norm of $g$ approaches (2).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .