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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Of course it does not..$f$ and $2^{2^{n}}f$ have the same sparsity in any basis. $\endgroup$– Sasho NikolovFeb 11, 2017 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 NikolovFeb 11, 2017 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$– gradstudentFeb 12, 2017 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 NikolovFeb 12, 2017 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 NikolovFeb 12, 2017 at 4:03
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
4
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$ Feb 12, 2017 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$ Feb 12, 2017 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$ Feb 12, 2017 at 6:52
-