-1
$\begingroup$

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?

$\endgroup$
  • $\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
1
$\begingroup$

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.

$\endgroup$
  • $\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.