Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$.

Given a function $f:[-1,1] \rightarrow[0,1]$, we can define for every $a \in \{0,1\}^d$ the Fourier coefficient $$\hat{h}_a = \sum_{r \in \{0,1\}^d}f\left(1-2\frac{|r|}{d}\right)(-1)^{\left<r,a\right>}$$ Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.

I am looking for an upper-bound on $\frac{1}{2^{d}}\|v\|_1$ in terms of $f$.

Thank you very much for your help.

  • $\begingroup$ Is this question motivated by something? You could compose $f$ with any other symmetric function of $r$, what is so special about the eigenvalues of the hypercube? $\endgroup$ – Sasho Nikolov Jun 8 '14 at 12:13
  • 1
    $\begingroup$ @SashoNikolov, thank you for your comment. It is motivated by the need to bound the induced infinity norm of $f(A)$, where $A$ is the normalized adjacency matrix of the Hypercube. $f$ itself is the normalized Féjer kernel. I thought the connection to the Fourier coefficients might simplify the problem. $\endgroup$ – Dean Jun 8 '14 at 12:21
  • 1
    $\begingroup$ In case $f$ maps to $\{0,1\}$, then $h(x) = f(1-2|x|/d)$ is a symmetric boolean function and then, your question is answered by cs.mcgill.ca/~aada/papers/AFH2012.pdf. $\endgroup$ – arnab Jun 8 '14 at 12:35
  • $\begingroup$ Thank you @arnab, but I discretization will not help here. However, this result does strengthen my intuition, that the upper bound is around $d$. $\endgroup$ – Dean Jun 8 '14 at 13:00

The question is about the spectral norm of the symmetric function $h: \{0,1\}^n \to [-1,+1]$ defined as $h(x) = f(1-2|x|/d)$. (I have assumed range $[-1,+1]$ instead of $[0,1]$ which is wlog by appropriate rescaling.)

Ada, Fawzi and H. Hatami show that for any boolean $g: \{0,1\}^n \to \{-1, +1\}$, $$\log \|\hat{g}\|_1 = \Theta\left(r(g) \log\left(\frac{n}{r(g)}\right)\right)$$ where $r(g) = \max(r_0(g), r_1(g))$ and $r_0(g)$ and $r_1(g)$ are minimum integers such that $g$ is either constant or perfectly correlated with parity or anti-parity for $x$ with $|x| \in [r_0(g), n-r_1(g)]$.

Now, look at the proof of Lemma 3.1 in the paper. Note that this straightforward argument also holds for functions $h$ mapping to $[-1,+1]$ instead of $\{-1,+1\}$. So, the same upperbound also holds for your case. This upperbound is tight at least for the boolean functions, but I don't know if there's a similar general lowerbound for non-boolean $h$.

  • $\begingroup$ You are right, I missed that. Thank you very much. $\endgroup$ – Dean Jun 9 '14 at 10:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.