<p>Hint: find a random variable <span class="math-container">$X=X(S)$</span> such that <span class="math-container">$\mathbf{E}[X]=\hat{||}f\hat{||}_1$</span> where the expectation is under the spectral sample. Use this to apply Markov to find an appropriate set with Fourier mass at least <span class="math-container">$1-\epsilon$</span>, and then argue that the size of the set must be at most the claimed cardinality.</p>

CC BY-SA 4.0
2023-03-25T15:45:30.593Z
Thanks for responding, just have a quick question. This approach seems to be assuming that the function is Boolean valued (so that total Fourier mass is equal to 1). Does scaling by $||f||_2^2$ give the same result for real-valued functions?
Ash
CC BY-SA 4.0
2023-03-23T15:46:09.043Z
2023-03-23T15:46:09.043Z
Jason Gaitonde
<p>Here is a direct construction:
<span class="math-container">$$F = \left\{S:|\hat{f}(S)|\ge \frac{\epsilon}{\hat{\|}f\hat{\|}_1}\right\}$$</span>
And you can verify the two conditions.</p>

CC BY-SA 4.0
2023-12-01T11:44:39.063Z
2023-12-01T11:45:11.840Z
2023-12-01T11:45:11.840Z
usercfp
<p><span class="math-container">$\newcommand{\R}{\mathbb{R}}$</span>
This question is about Problem 3.16 in Ryan O'Donnell's <em>Analysis of Boolean Functions</em> book. The problem is stated as follows:</p>
<blockquote>
<p>Let <span class="math-container">$f : \{-1,1\}^n\to\R$</span> and let <span class="math-container">$\epsilon&gt;0$</span>. Show that <span class="math-container">$f$</span> is <span class="math-container">$\epsilon$</span>-concentrated on a collection <span class="math-container">$F\subseteq 2^{[n]}$</span> with <span class="math-container">$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$</span>.</p>
</blockquote>
<p>Here, <span class="math-container">$\hat{||}f\hat{||}_1 := \sum_{S\subseteq [n]} |\widehat{f}(S)|$</span>, and <span class="math-container">$f$</span> being <span class="math-container">$\epsilon$</span>-concentrated on <span class="math-container">$F$</span> means <span class="math-container">$\sum_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$</span>. I have tried several approaches for this problem, and all seem to run into the pitfall of relating <span class="math-container">$\hat{||}f\hat{||}_1^2$</span> to <span class="math-container">$||f||_2$</span> (equivalently <span class="math-container">$\hat{||}f\hat{||}_2$</span> by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling <span class="math-container">$|\widehat{f}(S)|$</span> uniformly over <span class="math-container">$S$</span>, bounding the variance of this random variable, and applying Chebyshev's. But since <span class="math-container">$\mathbf{E}[|\widehat{f}(S)|]$</span> might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!</p>
<p><strong>Edit:</strong> I was eventually able to find a solution. As a hint, start by constructing a reasonable set <span class="math-container">$F$</span> which trivially satisfies <span class="math-container">$|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$</span>. To prove <span class="math-container">$\epsilon$</span>-concentration, recall the fairly simple technique used to bound <span class="math-container">$\sum \widehat{g}(S)^3$</span> in the analysis for the BLR test (Section 1.6 in <em>Analysis of Boolean Functions</em>).</p>

<boolean-functions>
Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm
Ash
# Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

(Asked by: username_0 on 2023-03-23)

$\newcommand{\R}{\mathbb{R}}$
This question is about Problem 3.16 in Ryan O'Donnell's *Analysis of Boolean Functions* book. The problem is stated as follows:

> Let $f : \{-1,1\}^n\to\R$ and let $\epsilon>0$. Show that $f$ is $\epsilon$-concentrated on a collection $F\subseteq 2^{[n]}$ with $|F|\leq \hat{||}f\hat{||}\_1^2/\epsilon$.

Here, $\hat{||}f\hat{||}\_1 := \sum\_{S\subseteq [n]} |\widehat{f}(S)|$, and $f$ being $\epsilon$-concentrated on $F$ means $\sum\_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$. I have tried several approaches for this problem, and all seem to run into the pitfall of relating $\hat{||}f\hat{||}\_1^2$ to $||f||\_2$ (equivalently $\hat{||}f\hat{||}\_2$ by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling $|\widehat{f}(S)|$ uniformly over $S$, bounding the variance of this random variable, and applying Chebyshev's. But since $\mathbf{E}[|\widehat{f}(S)|]$ might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!

**Edit:** I was eventually able to find a solution. As a hint, start by constructing a reasonable set $F$ which trivially satisfies $|F|\leq \hat{||}f\hat{||}\_1^2/\epsilon$. To prove $\epsilon$-concentration, recall the fairly simple technique used to bound $\sum \widehat{g}(S)^3$ in the analysis for the BLR test (Section 1.6 in *Analysis of Boolean Functions*).

**Tags:** boolean-functions


---

## 2 answers

### Answer by username_1 on 2023-03-23. Score: 1

Hint: find a random variable $X=X(S)$ such that $\mathbf{E}[X]=\hat{||}f\hat{||}\_1$ where the expectation is under the spectral sample. Use this to apply Markov to find an appropriate set with Fourier mass at least $1-\epsilon$, and then argue that the size of the set must be at most the claimed cardinality.

> **Comments:**
> **username_0**: Thanks for responding, just have a quick question. This approach seems to be assuming that the function is Boolean valued (so that total Fourier mass is equal to 1). Does scaling by $||f||_2^2$ give the same result for real-valued functions?  

---

### Answer by username_2 on 2023-12-01. Score: 1

Here is a direct construction:
$$F = \left\{S:|\hat{f}(S)|\ge \frac{\epsilon}{\hat{\|}f\hat{\|}\_1}\right\}$$
And you can verify the two conditions.


---

