4
$\begingroup$

Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity,

$\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $

i.e the sum of the sizes of the subsets of $[n]$ corresponding to the non-zero Fourier coefficients of the function.

  • Is there a nice "analytic" form for this quantity? Anything is known about this?
$\endgroup$
  • $\begingroup$ This is a very "discontinuous" quantity, as you can switch from zero to nonzero with an arbitrarily small change, so I doubt you will get a nice expression. What about something like $\sum_S \hat f(S)^2 |S|$? This is a continuous version of what you want. It is called the total influence and has a variety of properties. $\endgroup$ – Thomas Feb 20 '17 at 19:06
  • $\begingroup$ Yeah. Your quantity is more standard. I want to somehow analyze this sum without that Fourier weighting. Any "nice" way to set all the $\hat{f}(S)$ to $1$ whenever $\hat{f}(S) \neq 0$? $\endgroup$ – gradstudent Feb 20 '17 at 20:03
  • $\begingroup$ @Thomas The point you raise is interesting - do we know any characterization of what kind of small changes will turn on a specific Fourier mode? $\endgroup$ – gradstudent Feb 20 '17 at 20:14
  • $\begingroup$ Another commonly studied property is Fourier sparsity, which is $\sum_{\hat{f}(S) \neq \emptyset} 1$. Perhaps you can somehow relate the two. $\endgroup$ – Yuval Filmus Feb 20 '17 at 22:55
  • $\begingroup$ Well, since the Fourier basis is a linear basis, the condition for a coefficient to be zero is a linear condition. So although your quantity is discontinuous, it is still lower semi-continuous (analogous to the rank of a matrix). If you want to know what changes to a circuit will "turn on" a given Fourier mode, however, that sounds quite tricky and probably doesn't have a clean characterization. $\endgroup$ – Joshua Grochow Feb 21 '17 at 14:10

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.