2
$\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 $0$ bits and $1-b$ to $1$ 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 [n]$ as $\chi_S^b(x) = \prod_{i \in S} \chi_i^b(x)$. The collection $\{\chi_S^b \}$ over all $S \subset [n]$ is now our desired orthonormal basis. 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? Is there a general relation between $||f||_p$ and $||g||_p$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.