<p>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.)</p>

<p><a href="http://www.cs.mcgill.ca/~aada/papers/AFH2012.pdf" rel="nofollow">Ada, Fawzi and H. Hatami</a> show that for any <em>boolean</em> $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)]$. </p>

<p>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$.</p>

CC BY-SA 3.0
2014-06-09T10:24:23.660Z
You are right, I missed that. Thank you very much.
Dean
CC BY-SA 3.0
2014-06-09T05:28:59.037Z
2014-06-09T05:28:59.037Z
arnab
<p>Let $G$ be the normzlied <a href="http://mathworld.wolfram.com/HypercubeGraph.html" rel="noreferrer">hypercube graph</a> 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$. </p>

<p>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&lt;r,a\right&gt;}$$
Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.</p>

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

<p>Thank you very much for your help.</p>

CC BY-SA 3.0
2014-06-08T12:13:15.107Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-06-08T12:21:18.777Z
@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](http://en.wikipedia.org/wiki/Fej%C3%A9r_kernel). I thought the connection to the Fourier coefficients might simplify the problem.
Dean
CC BY-SA 3.0
2014-06-08T12:35:38.970Z
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 http://www.cs.mcgill.ca/~aada/papers/AFH2012.pdf.
arnab
CC BY-SA 3.0
2014-06-08T13:00:06.957Z
Thank you @arnab, but I discretization will not help here. However, this result does strengthen my intuition, that the upper bound is around $d$.
Dean
<cc.complexity-theory><graph-theory><fourier-analysis><gr.group-theory>
$\ell_1$ norm of Fourier coefficients vector for the hypercube
Dean
# $\ell_1$ norm of Fourier coefficients vector for the hypercube

(Asked by: username_0 on 2014-06-08)

Let $G$ be the normzlied [hypercube graph](http://mathworld.wolfram.com/HypercubeGraph.html) 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}$$
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.

**Tags:** cc.complexity-theory, graph-theory, fourier-analysis, gr.group-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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](http://en.wikipedia.org/wiki/Fej%C3%A9r_kernel). I thought the connection to the Fourier coefficients might simplify the problem.  
> **username_2**: 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 http://www.cs.mcgill.ca/~aada/papers/AFH2012.pdf.  
> **username_0**: Thank you @username_2, but I discretization will not help here. However, this result does strengthen my intuition, that the upper bound is around $d$.  

---

## 1 answers

### Answer by username_2 on 2014-06-09. Score: 3 | Accepted answer

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](http://www.cs.mcgill.ca/~aada/papers/AFH2012.pdf) 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$.

> **Comments:**
> **username_0**: You are right, I missed that. Thank you very much.  

---

