3
$\begingroup$

So I am trying to understand the scattering transform on graphs (GST). There are many formulations but I am stuck on equation 8 in this paper. Here they give a condition on a wavelets that looks like Equation 10 on page 7 of Mallat's foundational paper,and claim that this means that the wavelets were derived from a multi-resolution analysis (MRA).

If we look at the equations from Mallat, with the simplification that we specialize to $\mathbb{R}$ and the trivial subgroup consisting of just the identity, Mallat constructs a Littlewood-Paley Wavelet Transform by dilating $\psi\in L^2(\mathbb{R})$ with $\psi_j=2^j\psi(2^jx)$.

What I've been struggling with is understanding the following

  1. How the equations in Mallat's work are a "standard Littlewood-Paley condition"? I've seen Littlewood-Paley decompositions but that seems to tackle slightly different territory.

  2. How the equation in the first linked paper corresponds to a multi-resolution analysis?

I've read several good answers on here about the scattering transform itself, e.g. this one but understanding how Littlewood-Paley theory, Littlewood-Paley transforms, Littlewood-Paley conditions, and multi-resolution analysis (MRA)-derived wavelets are related.

Improve this question
$\endgroup$
10
  • $\begingroup$ I'm not too sure what you're asking. What "other LP" have you seen? And is (2) asking whether "LP = MRA"? $\endgroup$
    – OverLordGoldDragon
    Feb 23 at 11:40
  • 1
    $\begingroup$ I was hoping you'd see this, lol. @OverLordGoldDragon I have mostly seen LP in the books cited by Mallat, "Wavelets and Operators" by Myer and "Littlewood-Paley Theory and the Study of Function Spaces" which seem to cast it as approximating orthogonality in $L^p(\mathbb{R})$. Mallat seems to say the condition I'm confused about makes the scattering operator at scale $J$ unitary. Searching the mentioned books for 'unitary' doesn't yield a similar-looking equation. (2) Sort of. LP seems more general than MRA but how they are connected is beyond me. $\endgroup$
    – WedgeAntilles
    Feb 23 at 12:39
  • $\begingroup$ These all seem formally similar to equations 14 through 16 in the [deep scattering spectrum paper][arxiv.org/pdf/1304.6763.pdf] but the words 'Littlewood-Paley' don't appear there $\endgroup$
    – WedgeAntilles
    Feb 23 at 12:45
  • $\begingroup$ So (1) is partly asking why "LP = unitary"? Well frankly my linear algebra's not great and I don't know what "unitary" means, so I looked it up and certainly CWT doesn't qualify per the only definition I found, that's "self * adjoint = identity". It's true roughly, but the part that's untrue is lot more important - so I need to know how "unitary" is defined here. $\endgroup$
    – OverLordGoldDragon
    Feb 23 at 13:03
  • $\begingroup$ I believe in this setting it's 'norm-preserving' so the map taking a function to its wavelet decomposition is claimed to not lose any energy $\endgroup$
    – WedgeAntilles
    Feb 23 at 13:08

1 Answer 1

Reset to default
1
$\begingroup$

General remarks

I'm not familiar with Littlewood-Paley theory beyond the norm-preserving equation and its significance, or the concept of "unitary" beyond "self * adjoint = identity", but here's what I do know.

The criterion assures invertibility, and the "decomposition" property of the transform (as opposed to generative), as explained in the referenced post. This comes with important benefits, including information non-duplication (the frequency axis is tiled uniformly and filters complement each other), and uniformity of representation along frequency (L1 norm, see "L2 norm" here) - which enables spatial operators along said axis like convolutions (what's done in Joint Time-Frequency Scattering).

LP & MRA

One doesn't imply the other; LP can also be satisfied with STFT. What's important is, we seek kernels localized in frequency, but also that the filterbank captures the entire input, meaning there's necessarily multiple kernels. Per LP, these kernels must also sum to unity. STFT and CWT both have a "generating rule" of next kernel from previous: under STFT, it's frequency shift, and under CWT, it's a dilation while preserving zero-mean. Turns out, the appropriate generating rule is all that's needed, and any $\psi$ will work (with caveats) - covered here.

These are all my thoughts, I don't know if it's the formal justification.

Re: question points

How the equations in Mallat's work are a "standard Littlewood-Paley condition"? I've seen Littlewood-Paley decompositions but that seems to tackle slightly different territory.

Following the comments, there's "approximate orthogonality" in that wavelets sufficiently separated in frequency are uncorrelated. But I certainly disagree with thinking of this as "orthogonality" as great redundancy is a central trait of CWT. It is important that "sufficient separation = uncorrelated", though, for sake of sparsity and time-frequency resolution.

How the equation in the first linked paper corresponds to a multi-resolution analysis?

It can certainly be misleading to write as the paper does, "MRA i.e. LP". The L2-normed CWT is a galaxy away from LP, but it's still MRA.

I know zilch about graph convolutions, but I can conceptually generalize in that, it's still spatial operators in the sense of taking a number of input points and producing a number of output points that satisfy the same properties as regular convolutions. The core difference is potential non-uniformity and non-ordinality of inputs, unsure how they deal with that.

at scale $J$

The idea is, we wish to restrict the support of the largest wavelet, since e.g. there's no infinitely large cat - and the remaining frequencies will be tiled by a lowpass filter that's designed to complement the filterbank (satisfy LP). Moreover, as wavelets are zero-mean by definition, they'll never tile the DC bin, so again a need for lowpass.

But, caveat: practically we don't immediately follow up the last CWT wavelet with lowpass, instead we tile with wavelets of same scale but spaced linearly in frequency, i.e. STFT except zero-mean enforcement. It must be that Mallat's filterbank parameter choices permit to skip this step, but it's not a good idea in practice.

why, in that same paper, equation 14 satisfies equation 15

The theoretic answer is given here. The practical answer is - quoting (emphasis mine), "The wavelet and the low-pass are designed to ..." - they certainly don't in general, we make it happen.

why one would look for equations/statements of that form

The form simply includes all filters used in the transform - completeness.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for a wonderful answer! The way that graph "wavelets" work, at least in the undirected weighted setting, is by applying a set of functions to the spectrum of the (normalized) graph Laplacian. In the graph scattering paper the functions they apply are wavelets derived from an MRA. The claim seems to be if we take a scaling function $\phi$ and wavelets $\psi_j$ derived from an MRA, then they satisfy the following equation (call it (1)) $|\hat{\phi}_{-J}(\omega)||^2 + \sum_{j>-J}|\hat{\psi}(\omega)|^2 = 1$ My question is: is it true MRA implies (1) and if so why? $\endgroup$
    – WedgeAntilles
    Feb 23 at 14:48
  • $\begingroup$ @WedgeAntilles I did address that in the answer, but to add to it - L1 normed CWT doesn't necessarily satisfy it, and the counter-example, of all things, is Morlet wavelets! To explain further would be to expand the scope of the question beyond what's acceptable on Stack Exchange, so it should be asked separately. $\endgroup$
    – OverLordGoldDragon
    Feb 23 at 14:53
  • $\begingroup$ I have asked the question here: dsp.stackexchange.com/q/86789/66638 $\endgroup$
    – WedgeAntilles
    Feb 24 at 3:55
  • $\begingroup$ @WedgeAntilles I got thrown off in this answer by one of the caveats. Good question, I learned something! $\endgroup$
    – OverLordGoldDragon
    Feb 24 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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