Sparsity in Hadamard & Fourier transform

Question

I heard somewhere the statement that if $x\in \mathbb{R}^n$ is sparse, then $Fx$ and $Hx$ cannot be too sparse. Here, $F,H$ refer to the Fourier transform and Hadamard transform respectively. Can someone shed some intuition on what these transforms are doing? And as a result, why this statement is true?

Answer 1

So, the transforms are used to simplify signal representation. However, if the representation is simple in one domain (time, say, such as a dirac delta) then it is complex (has many nonzero coefficients). This is generally referred to as an uncertainty principle.

Terry Tao has a nice blogpost here about this phenomenon. For example he mentions the following intuitive properties:

• A function which is band-limited (restricted to low frequencies) is featureless and smooth at fine scales, but can be oscillatory (i.e. containing plenty of cancellation) at coarse scales. Conversely, a function which is smooth at fine scales will be almost entirely restricted to low frequencies.
• A function which is restricted to high frequencies is oscillatory at fine scales, but is negligible at coarse scales. Conversely, a function which is oscillatory at fine scales will be almost entirely restricted to high frequencies. Projecting a function to low frequencies corresponds to averaging out (or spreading out) that function at fine scales, leaving only the coarse scale behaviour.

Consider the DFT which you call $y=Fx$ with the signal and transform having dimension $n.$ Let $w(v)$ be the number of nonzero coefficients of a vector. Then there is an uncertainty principle that $$ w(x) w(y) \geq n $$ In fact if $n=pq$ is a nontrivial factorization of $n$ you can have a signal of weight $p=w(x)$ and its transform of weight $q=w(y),$ for example. This follows from group properties,since you are using a primitive root $w$ of order $n$ but $\xi=w^p$ of order $q$ represents signals of length $n/q=p$ so you could have a signal and its tansform supported on sparse sets. If $n$ is a perfect square then both the signal and its transform can have weight $\sqrt{n}$ and be equally sparse.

Finally, if $n$ is a prime then Terry Tao has recently proved that the stronger lower bound $$ w(x)+w(y)\geq n+1 $$ holds.