2
$\begingroup$

I was reading some of the MATLAB documentation and I get confused when reading the part about When is Continuous Analysis More Appropriate than Discrete Analysis?

My knowledge before reading the documentation:

I always thought that a signal that is non-differentiable everywhere requires an infinite number of terms to represent it. This is true for the Fourier basis and a wavelet basis.

The documentation:

To answer this, consider the related questions: Do you need to know all values of a continuous decomposition to reconstruct the signal exactly? Can you perform nonredundant analysis? When the energy of the signal is finite, not all values of a decomposition are needed to exactly reconstruct the original signal, provided that you are using a wavelet that satisfies some admissibility condition.

What I find confusing:

The documentation seems to imply that if the “energy of the signal is finite”, then you don’t need all the terms in the basis expansion. I don’t think this is true, because I can think of signals with finite energy, that are not differentiable everywhere. And if they aren’t differentiable everywhere, then they will require an infinite number of terms to represent using the Fourier basis or the wavelet basis. A perfect example of this is the boxcar function.

Is the documentation wrong?

$\endgroup$
  • 1
    $\begingroup$ Does it depend on the basis used? $\endgroup$ – Hunle Mar 21 '17 at 1:42
  • 1
    $\begingroup$ I would say that there is no "fundamental" difference among the orthogonal bases. However, when you move to frames, then you can have quite different behavior. Should I expend the part on frames versus bases? $\endgroup$ – Laurent Duval Mar 26 '17 at 9:56
  • 1
    $\begingroup$ In your statement: "I always thought that a signal that is non-differentiable everywhere requires an infinite number of terms to represent it..." do you actually mean not differentiable instead of non-differentiable, because otherwise you refer to a signal whose derivate does not exist on any point, if it's non-differentiable everywhere...? Or you can rephrase is as non-differentiable at some countable number of points Also you shall better ask this to MathWorks... $\endgroup$ – Fat32 Mar 28 '17 at 8:50
  • $\begingroup$ relatd: dsp.stackexchange.com/questions/8009/… $\endgroup$ – Hunle Apr 21 '17 at 23:54
  • $\begingroup$ That's a good point @Fat32 $\endgroup$ – Hunle Apr 21 '17 at 23:54
1
$\begingroup$

Matlab is not wrong. But let's look at your following sentence more carefully:

And if they aren’t differentiable everywhere. A discontinuity in the input function can be interpreted as an infinite bandwidth, hence it will require an infinite number of Fourier terms to represent using the Fourier basis or the wavelet basis.

Now this is true for the Fourier series since the basis functions are all differentiable. A jump discontinuity in the input function can be interpreted as an infinite bandwidth, hence it will require an infinite number of Fourier terms. The Gibbs phenomenon i.e. large overshoots and oscillations occur at the neighborhood of such discontinuities when dealing with truncated Fourier sums and the overshoots won't improve by increasing the terms.

Indeed, something similar can also happen in wavelets under specific conditions. This reference [after equation 15] provides the necessary and sufficient condition.

That said, when it comes to wavelets there is a difference. We can have wavelets that have discontinuities. So the number of terms is not necessary to be infinite for them to perfectly analyze/reconstruct an input function with jump discontinuity.

The most obvious example is the Haar wavelet which uses square-shaped basis functions. I mention this wavelet, particularly to address your boxcar signal example. This property of Haar transform is widely known. For example see here.

In the following picture from here there is an interesting and intuitive connection between the orthogonal "box" basis and Haar wavelet basis.

enter image description here

I would also suggest looking at the explanation as well as the last example in that reference.

$\endgroup$
1
$\begingroup$

[EDIT] Let us start from a verbose and simple example. In $\mathbb{R}^2$, the Mercedes-Benz pattern constitute a tight frame: redundant, energy-preserving:

Mercedes-Benz tight frame

Each vector $x=[x_1,x_2]$ yields three three projections $[p1,p2,p3]$, from which you can recover $x$ in a number of robust ways: if the projection value are corrupted, rounded, even if one is cancelled, you can still recover $x$, at least approximately. Because of the redundancy $2\to 3$ in the representation. This is not the case with the orthogonal basis the $\{[1,0],[0,1]\}$: if you lose one projection, $x$ is almost lost (you only keep one direction).

In other words, you don't need all coefficients with a frame of vectors (or wavelets). This basic example extends to more generic frames or bases. You can find more on that within the topic of oversampled filter banks, and the paper Filter bank frame expansions with erasures. Those are used for redundant channel coding, for instance.

In the continuous setting (both the signal and the wavelet transform), due to the huge redundancy, many possible inverses exist. Notably, given an analysis wavelet, the requirements on the synthesis wavelets to verify the admissibility conditions (on a pair of wavelets) are very mild. On these topics, I would suggest two references:

  • Matthias Holschneider, Wavelets, an analysis tool, 1995
  • Bruno Torrésani, Analyse continue par ondelettes, 1995

The topic is quite involved, may involve a lot of complicated functions spaces, different for the wavelets and the signals. A wavelet analysis is given by:

\begin{equation} W_f(b,a)\ =\ \int_{\mathbb{R}}\ f(t)\ \tfrac{1}{\sqrt{a}}\,\psi^{*}(\tfrac{t-b}{a})\ d t\ . \end{equation} Provided that $\psi$ is admissible, i.e. when the two constants $c^{\pm}_{\psi} = 2\pi \int_{0}^{+\infty}\tfrac{|\hat\psi(\pm\omega)|^{2}}{\omega} d\omega < \infty$ are finite and equal\footnote{When $\psi$ is sufficiently regular, this condition reduces to a zero-average requirement, that is, $\int_{\mathbb{R}} \psi(t)\ d t = 0$}, that is, $c^+_\psi=c^-_\psi=c_\psi < \infty$, the signal $f$ may be recovered from the coefficients $W_f(b,a)$: \begin{equation} f(t)\ =\ \tfrac{1}{c_{\psi}}\int_{0}^{+\infty}\!\!\!\int_{\mathbb{R}}\ W_f(b,a)\ \psi_{(b,a)}(t)\ d b\,\tfrac{d a}{a^{2}}. \end{equation}

You can find about the same idea in Torrésani's book, page 20: Torresani's book, p. 20

Still considering a continuous signal with finite energy, but trying to build a discretized wavelet frame, you can sample in the wavelet space with perfect reconstruction provided the sampling is dense enough with respect to some lower bound computed from the wavelet. So effectively, you don't need all (continuous) values. But the number of samples needed could be denombrable.

Basically, you have a frame when for every unit energy signal $f$ projected onto the set of frame elements $\psi_n$:

$$A\le \sum |<f,\psi_n>| \le B\,.$$

If $A=B=1$, you recover the case of orthogonal expansions. Ingrid Daubechies (for one) showed, from the continuous formula above, that one can find some discretizations $a_n$ and $b_n$ to build frame elements

$$\psi_n = \psi(\tfrac{t-b_n}{a_n})$$

and recover $f$ from the $|<f,\psi_n>| $, sometimes with iterative formulae that converge faster if $A$ is close to $B$.

Moving on to discrete signals (where differentiability is not well-defined), you can build unions of wavelet basis, or wavelet frames like the stationary wavelet transform. In this redundant (but with a finite number of samples) expansion, you can pick a subset of samples, that corresponds to, at minimum, a specific choice of basis vectors. Once again, you do not need all samples.

THe rationale is that if an $N$ sample signal get represented by $M> N$ coefficients, when they are well formed (frame coefficients for instance), different inverses exist, some of then discarding parts of coefficients.

For a basis (non redundant) expansion however, all samples are required in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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