For a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ one can ask for its $l_0$ norm in the indicator basis i.e the number of vertices on which the function is non-zero. Does this sparsity parameter have any bearing (or the otherway) on how large can the largest non-zero term be in its Fourier expansion?


closed as unclear what you're asking by Sasho Nikolov, D.W., Mohammad Al-Turkistany, Yuval Filmus, gradstudent Feb 20 '17 at 17:06

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Of course it does not..$f$ and $2^{2^{n}}f$ have the same sparsity in any basis. $\endgroup$ – Sasho Nikolov Feb 11 '17 at 22:20
  • $\begingroup$ Your questions should demonstrate some minimal understanding of the subject matter. A question of this type is more appropriate at Math.SE if anywhere. $\endgroup$ – Sasho Nikolov Feb 11 '17 at 22:22
  • $\begingroup$ @SashoNikolov I did not understand your objection to the question I asked. Maybe my wording isn't clear. Can you please check the comment I made below Areyh's answer. Just in case my clarification helps! $\endgroup$ – gradstudent Feb 12 '17 at 1:35
  • $\begingroup$ Your wording indeed seems unclear. "[L]argest non-zero term" to me means largest in absolute value. This clearly has no connection to sparsity. Are you asking about a relationship between sparsity and degree? $\endgroup$ – Sasho Nikolov Feb 12 '17 at 3:46
  • 2
    $\begingroup$ There are only slightly less trivial examples that show you cannot say much: large degree functions can be both very sparse or very dense. Something you can say is the uncertainty principle: $\|f\|_0 \|\hat{f}\|_0 \ge 2^n$. $\endgroup$ – Sasho Nikolov Feb 12 '17 at 4:03

The Fourier transform is a linear operation. In particular, for $f:\{-1,1\}\to\mathbb{R}$ and $S\subseteq[n]$, the Fourier coefficient $\hat f(S)$ is a linear functional of $f$. If $\hat f(S)\neq 0$, its magnitude can be made arbitrarily large or small by multiplying $f$ by an appropriate scalar -- without affecting $||f||_0$. So the answer to your question is negative.

  • $\begingroup$ Yes. But I think my question was the other way round. If one fixes the sparsity of $f$ then does that still allow for large Fourier degrees to be non-zero? Like see the "parity" function. I will call it highly non-sparse because on half the vertices it is non-zero. And "correspondingly" its non-zero Fourier coefficient is the largest it could be. Is there any underlying phenomenon here? $\endgroup$ – gradstudent Feb 12 '17 at 1:24
  • $\begingroup$ Exercise: what is the Fourier transform of the indicator function of the singleton set $\{1\}$, where $1$ is the all-ones vector? I.e. the function $f(1, \ldots, 1) = 1$ and $f(x) = 0$ for any other $x$. $\endgroup$ – Sasho Nikolov Feb 12 '17 at 3:59
  • $\begingroup$ Yes. Since the examples do seem to go both ways, it raises the question if there is any implication at all. Maybe atleast a one-way implication exists? $\endgroup$ – gradstudent Feb 12 '17 at 6:52
  • $\begingroup$ I think the answer is nope $\endgroup$ – ivmihajlin Feb 17 '17 at 0:54

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