Group Invariant Scattering

Introduction

Since $\Phi$ is translation invariant, the Lipschitz upper bound does not depend upon the maximum translation amplitude $\sup_{x}|\tau(x)|$ of the diffeomorphism metric (1). The Lipschitz continuity (2) implies that $\Phi$ is invariant to global translations, but it is much stronger. $\Phi$ is almost invariant to “local translations” by $\tau(x)$, up to the first and second order deformation terms.

The representation of stationary processes with the Fourier power spectrum results from the translation invariance of the Fourier modulus. Similarly, Section 4 defines an expected scattering transform which maps stationary processes to an ${\bf l}^{2}$ space. Scattering coefficients depend upon high order moments of stationary processes, and can thus discriminate processes having same second-order moments. As opposed to the Fourier spectrum, a scattering representation is Lipschitz continuous to random deformations up to a log term. For large classes of ergodic processes, it is numerically observed that the scattering transform of a single realization provides a mean-square consistent estimator of the expected scattering transform.

A software package is available at www.cmap.polytechnique.fr/scattering, to reproduce numerical experiments. Applications to audio and image classification can be found in .

Finite Path Scattering

Since $|\xi|$ can be arbitrarily large, $\Phi(f)=|\hat{f}|$ does not satisfy the Lipschitz continuity condition (2) when scaling high frequencies. The frequency displacement from $\xi$ to $(1-s)\,\xi$ has a small impact if sinusoidal waves are replaced by localized functions having a Fourier support which is wider at high frequencies. This is achieved by a wavelet transform , whose properties are briefly reviewed in this section.

Its Fourier transform is $\hat{\psi}_{2^{j}r}(\omega)=\hat{\psi}(2^{-j}r^{-1}\omega)$. A scattering transform is computed with wavelets that can be written

If $f$ is real then $\hat{f}(-\omega)=\hat{f}^{*}(\omega)$ and if $\hat{\psi}(\omega)$ is real then $W[-\lambda]f=W[\lambda]f^{*}$. Let ${G}^{+}$ denote the quotient of ${G}$ with $\{-{\mathbf{1}}\,,\,{\mathbf{1}}\}$, where two rotations $r$ and $-r$ are equivalent. It is sufficient to compute $W[2^{j}r]f$ for “positive” rotations $r\in G^{+}$. If $f$ is complex then $W[2^{j}r]f$ must be computed for all $r\in G=G^{+}\times\{-{\mathbf{1}},{\mathbf{1}}\}$.

A wavelet transform at a scale $2^{J}$ only keeps wavelets of frequencies $2^{j}>2^{-J}$. The low frequencies which are not covered by these wavelets are provided by an averaging over a spatial domain proportional to $2^{J}$:

If $f$ is real then the wavelet transform W_{J}f=\Big{\{}A_{J}f\,,\,\Bigl{(}W[\lambda]f\Bigr{)}_{\lambda\in{\Lambda}_{J}}\Bigr{\}} is indexed by ${\Lambda}_{J}=\{\lambda=2^{j}r\,:\,r\in{G}^{+}\,,\,2^{j}>2^{-J}\}$. Its norm is

where $\beta=1$ for complex functions and $\beta=1/2$ for real functions.

Proof: If $f$ is complex, $\beta=1$ and one can verify that (9) is equivalent to

Since $\widehat{W[2^{j}r]f}(\omega)=\hat{f}(\omega)\,\hat{\psi}_{2^{j}r}(\omega)$, multiplying (10) by $|\hat{f}(\omega)|^{2}$, and applying the Plancherel formula proves that $\|W_{J}f\|^{2}=\|f\|^{2}$. For $J=\infty$ the same result is obtained by letting $J$ go to $\infty$.

Conversely, if $\|W_{J}f\|^{2}=\|f\|^{2}$ then (10) is satisfied for almost all $\omega$. Otherwise, one can construct a function $f\neq 0$ where $\hat{f}$ has a support in the domain of $\omega$ where (10) is not valid. With the Plancherel formula we verify that $\|W_{J}f\|^{2}\neq\|f\|^{2}$, which contradicts the hypothesis.

If $f$ is real then $|\hat{f}(\omega)|=|\hat{f}(-\omega)|$ so $\|W[2^{j}r]f\|=\|W[-2^{j}r]f\|$. Hence $\|W_{J}f\|$ remains the same if $r$ is restricted to $G^{+}$ and $\psi$ is multiplied by $\sqrt{2}$, which yields condition (9) with $\beta=1/2$. $\Box$

In all the following, $\hat{\psi}$ is a real function which satisfies the unitary condition (9). It implies that $\hat{\psi}(0)=\int\psi(x)\,dx=0$ and $|\hat{\phi}(r\omega)|=|\hat{\phi}(\omega)|$ for all $r\in{G}$. We choose $\hat{\phi}(\omega)$ to be real and symmetric so that $\phi$ is also real and symmetric and $\phi(rx)=\phi(x)$ for all $r\in{G}$. We also suppose that $\phi$ and $\psi$ are twice differentiable and that their decay as well as the decay of their partial derivatives of order $1$ and $2$ is $O((1+|x|)^{-d-2})$.

Since $\phi$ is invariant to rotations in $G$ we verify that $A_{J}$ commutes with rotations in $G$: $A_{J}(g\circ f)=g\circ A_{J}f$ for all $g\in G$.

In dimension $d=1$, ${G}=\{-{\mathbf{1}},{\mathbf{1}}\}$. According to (5), to build a complex wavelet $\psi$ concentrated on a single frequency band, we set $\hat{\psi}(\omega)=0$ for $\omega<0$. Following (9), $W_{J}$ is unitary if and only if

The one-dimensional function $\hat{\psi}(|\omega|)$ is chosen to satisfy (12). The Littlewood-Paley condition (9) is then equivalent to

2 Path Ordered Scattering

Convolutions with wavelets defines operators which are Lipschitz continuous to the action of diffeomorphisms, because wavelets are regular and localized functions. However, a wavelet transform is not invariant to translations, and $W[\lambda]f=f\star\psi_{\lambda}$ translates when $f$ is translated. The main difficulty is to compute translation invariant coefficients, which remain stable to the action of diffeomorphisms, and retain high frequency information provided by wavelets. A scattering operator computes such a translation invariant representation. We first explain how to build translation invariant coefficients from a wavelet transform, while maintaining stability to the action of diffeomorphisms. Scattering operators are then defined, and their main properties are summarized.

If $\psi(x)=e^{i\eta\cdot x}\theta(x)$ then $\psi_{\lambda}(x)=e^{i\lambda\eta\cdot x}\,\theta_{\lambda}(x)$, and hence

The convolution $f^{\lambda}\star\theta_{\lambda}$ is a low-frequency filtering because $\hat{\theta}_{\lambda}(\omega)=\hat{\theta}(\lambda^{-1}\omega)$ covers a frequency ball centered at $\omega=0$, of radius proportional to $|\lambda|$. A non-zero invariant can thus be obtained by canceling the modulation term ${\rm e}^{i\lambda\eta\cdot x}$ with $M[\lambda]$. A simple example is:

where $\Phi(\hat{h}(\lambda\eta))$ is the complex phase of $\hat{h}(\lambda\eta)$. This non-linear phase registration guarantees that $M[\lambda]$ commutes with translations. It results from (13) that $\int{M[\lambda]W[\lambda]f(x)}\,dx=|\hat{f}(\lambda\eta)|\,|\hat{\theta}(0)|$. It recovers the Fourier modulus representation, which is translation invariant but not Lipschitz continuous to diffeomorphisms as shown in (3). Indeed, the demodulation operator $M[\lambda]$ in (14) commutes with translations but does not commute with the action of diffeomorphisms, and in particular with dilations. The commutator norm of $M[\lambda]$ with a dilation is equal to $2$, even for arbitrarily small dilations, which explains the resulting instabilities.

Lower frequencies created by a modulus result from interferences. For example, if $f(x)=\cos(\xi_{1}\cdot x)+a\,\cos(\xi_{2}\cdot x)$ where $\xi_{1}$ and $\xi_{2}$ are in the frequency band covered by $\hat{\psi}_{\lambda}$ then $|f\star\psi_{\lambda}(x)|=2^{-1}|\hat{\psi}_{\lambda}(\xi_{1})\,+a\,\hat{\psi}_{\lambda}(\xi_{2})\,e^{i(\xi_{2}-\xi_{1})\cdot x}|$ oscillates at the interference frequency $|\xi_{2}-\xi_{1}|$, which is smaller than $|\xi_{1}|$ and $|\xi_{2}|$.

The integration $\int U[\lambda]f(x)\,dx=\int|f\star\psi_{\lambda}(x)|\,dx$ is translation invariant but it removes all the high frequencies of $|f\star\psi_{\lambda}(x)|$. To recover these high frequencies, a scattering also computes the wavelet coefficients of each $U[\lambda]f$: $\{U[{\lambda}]f\star\psi_{\lambda^{\prime}}\}_{\lambda^{\prime}}$. Translation invariant coefficients are again obtained with a modulus $U[\lambda^{\prime}]U[\lambda]f=|U[\lambda]f\star\psi_{\lambda^{\prime}}|$ and an integration $\int U[\lambda^{\prime}]U[\lambda]f(x)\,dx$. If $f(x)=\cos(\xi_{1}\cdot x)+a\,\cos(\xi_{2}\cdot x)$ with $a<1$, $|\xi_{2}-\xi_{1}|\ll|\lambda|$ and $|\xi_{2}-\xi_{1}|$ in the support of $\hat{\psi}_{\lambda^{\prime}}$ then $U[\lambda^{\prime}]U[\lambda]f$ is proportional to $a\,|\psi_{\lambda}(\xi_{1})|\,|\psi_{\lambda^{\prime}}(|\xi_{2}-\xi_{1}|)|$. The second wavelet $\hat{\psi}_{\lambda^{\prime}}$ captures the interferences created by the modulus, between the frequency components of $f$ in the support of $\hat{\psi}_{\lambda}$. We now introduce the scattering propagator, which extends these decompositions.

Section 2.1 explains that if $f$ is complex valued then its wavelet transform is $W_{\infty}f=\{W[\lambda]f\}_{\lambda\in\Lambda_{\infty}\atop-\lambda\in\Lambda_{\infty}}$ whereas if $f$ is real then $W_{\infty}f=\{W[\lambda]f\}_{\lambda\in\Lambda_{\infty}}$. If $f$ is complex then at the next iteration $U[\lambda_{1}]f=|W[\lambda_{1}]f|$ is real so next stage wavelet transforms are computed only for $\lambda_{k}\in{\Lambda}_{\infty}$. The scattering propagator of a complex function is thus defined over “positive” paths $p=(\lambda_{1},\lambda_{2},...,\lambda_{m})\in{\Lambda}_{\infty}^{m}$ and “negative” paths denoted $-p=(-\lambda_{1},\lambda_{2},...,\lambda_{m})$. This is analogous to the positive and negative frequencies of a Fourier transform. If $f$ is real then $W[-\lambda_{1}]f=W[\lambda_{1}]f^{*}$ so $U[-\lambda_{1}]f=U[\lambda_{1}]f$ and hence $U[-p]f=U[p]f$. To simplify explanations, all results are proved on real functions with scattering propagators restricted to positive paths. These results apply to complex functions by including negative paths.

If $p\neq{\emptyset}$ then ${\overline{S}}f(p)$ is non-linear but it preserves amplitude factors:

A scattering has similar scaling and rotation covariance properties as a Fourier transform. If $f$ is scaled and rotated, ${2^{l}g}\circ f(x)=f(2^{l}gx)$, then (11) implies that $U[\lambda](2^{l}g\circ f)=2^{l}g\circ U[{2^{-l}g\lambda}]f$ and cascading this result shows that

Inserting this result in the definition (18) proves that

The convolution with $\phi_{2^{J}}(x)=2^{-dJ}\phi(2^{-J}x)$ localizes the scattering transform over spatial domains of size proportional to $2^{J}$:

It defines an infinite family of functions indexed by ${\mathcal{P}}_{J}$, denoted

For complex-valued functions, negative paths are also included in ${\mathcal{P}}_{J}$, and $S_{J}[-p]f=S_{J}[p]f$ if $f$ is real.

Section 2.3 proves that for appropriate wavelets, $\|f\|^{2}=\sum_{p\in{\mathcal{P}}_{J}}\|S_{J}[p]f\|^{2}$. However, the signal energy is mostly concentrated on a much smaller set of frequency-decreasing paths $p=(\lambda_{k})_{k\leq m}$ for which $|\lambda_{k+1}|\leq|\lambda_{k}|$. Indeed, the propagator $U[\lambda]$ progressively pushes the energy towards lower frequencies. The main theorem of Section 2.5 proves that a windowed scattering is Lipschitz continuous to the action of diffeomorphisms.

3 Scattering Propagation and Norm Preservation

A windowed scattering can be computed by iterating on the one-step propagator defined by

with $A_{J}f=f\star\phi_{2^{J}}$ and $U[\lambda]f=|f\star\psi_{\lambda}|$. After calculating $U_{J}f$, applying again ${U}_{J}$ to each $U[\lambda]f$ yields a larger infinite family of functions. The decomposition is further iterated by recursively applying ${U}_{J}$ to each $U[p]f$. Since $U[\lambda]U[p]=U[p+\lambda]$ and $A_{J}U[p]=S_{J}[p]$, it results that

Let ${\Lambda}_{J}^{m}$ be the set of paths of length $m$, with ${\Lambda}_{J}^{0}=\{{\emptyset}\}$. It is propagated into

Scattering calculations follow the general architecture of convolution neural-networks introduced by LeCun . Convolution networks cascade convolutions and a “pooling” non-linearity, which is here the modulus of a complex number. Convolution networks typically use kernels that are not predefined functions such as wavelets, but which are learned with backpropagation algorithms. Convolution network architectures have been successfully applied to number of recognition tasks and are studied as models for visual perception . Relations between scattering operators and path formulations of quantum field physics are also studied in .

Since ${W_{J}}$ is unitary, setting $h=0$ also proves that $\|{U_{J}}f\|=\|f\|$, so ${U_{J}}$ preserves the norm.

For any path set $\Omega$ the norms of $S_{J}[\Omega]f$ and $U[\Omega]f$ are

Since $S_{J}[{\mathcal{P}}_{J}]$ iterates on $U_{J}$ which is nonexpansive, the following proposition derives that $S_{J}[{\mathcal{P}}_{J}]$ is also nonexpansive.

The scattering transform is nonexpansive:

Proof: Since ${U_{J}}$ is nonexpansive, it results from (25) that

Summing these equations for $m$ going from to $\infty$ proves that

Section 2.2 explains that each $U[\lambda]f=|f\star\psi_{\lambda}|$ captures the frequency energy of $f$ over a frequency band covered by $\hat{\psi}_{\lambda}$ and propagates this energy towards lower frequencies. The following theorem proves this result by showing that the whole scattering energy ultimately reaches the minimum frequency $2^{-J}$ and is trapped by the low-pass filter $\phi_{2^{J}}$. The propagated scattering energy thus goes to zero as the path length increases, and the theorem derives that $\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$. This result also applies to complex-valued functions by incorporating negative paths $(-\lambda_{1},\lambda_{2},...,\lambda_{m})$ in ${\mathcal{P}}_{J}$.

Summing for $m\leq n<\infty$ proves that $\lim_{m\rightarrow\infty}\|U[{\Lambda}^{m}_{J}]f\|=0$ is equivalent to $\lim_{m\rightarrow\infty}\sum_{n=m}^{\infty}\|S_{J}[{\Lambda}^{n}_{J}]f\|^{2}=0$. Since $f=U[{\Lambda}^{0}_{J}]f$, summing (33) for $0\leq n<m$ also proves that

so $\|S_{J}[{\mathcal{P}}_{J}]f\|^{2}=\sum_{n=0}^{\infty}\|S_{J}[{\Lambda}^{n}_{J}]f\|^{2}=\|f\|^{2}$ if and only if $\lim_{m\rightarrow\infty}\|U[{\Lambda}_{J}^{m}]\|=0$.

We now prove that condition (29) implies that $\lim_{m\rightarrow\infty}\|U[{\Lambda}_{J}^{m}]f\|^{2}=0$. It relies on the following lemma, which gives a lower bound of $|f\star\psi_{\lambda}|$ convolved with a positive function.

Appendix A uses this lemma to show that the scattering energy propagates progressively towards lower frequencies, and proves the following lemma.

Since $U[{\Lambda}^{m}]$ is nonexpansive $\|U[{\Lambda}^{m}_{J}]f-U[{\Lambda}^{m}_{J}]f_{n}\|\leq\|f-f_{n}\|$ so

The proof shows that the scattering energy propagates progressively towards lower frequencies. The energy of $U[p]f$ is mostly concentrated along frequency-decreasing paths $p=(\lambda_{k})_{k\leq m}$ for which $|\lambda_{k+1}|<|\lambda_{k}|$. For example, if $f=\delta$ then paths of length $1$ have an energy $\|U[2^{j}r]\delta\|^{2}=\|\psi_{2^{j}r}\|^{2}=2^{-dj}\|\psi\|^{2}$. This energy is then propagated among all paths $p\in{\mathcal{P}}_{J}$. For a cubic spline wavelet in dimension $d=1$, over $99.5\%$ of this energy is concentrated along frequency-decreasing paths. Numerical implementations of scattering transforms thus limits computations to these frequency decreasing paths. The scattering transform of a signal of size $N$ is computed along all frequency-decreasing paths, with $O(N\log N)$ operations, by using a filter bank implementation .

The decay of $\sum_{n=m}^{\infty}\|S_{J}[{\Lambda}^{n}_{J}]f\|^{2}$ implies that we can neglect all paths of length larger than some $m>0$. The numerical decay of $\|S_{J}[{\Lambda}^{n}_{J}]f\|^{2}$ appears to be exponential in image and audio processing applications. The path length is limited to $m=3$ in classification applications .

4 Translation Invariance

We show that the scattering distance $\|S_{J}[{\overline{\mathcal{P}}}_{J}]f-S_{J}[{\overline{\mathcal{P}}}_{J}]h\|$ is non-increasing when $J$ increases, and thus converges when $J$ goes to $\infty$. It defines a limit distance which is proved to be translation invariant. Section 3 studies the convergence of $S_{J}[{\mathcal{P}}_{J}]f$ when $J$ goes to $\infty$, to the translation invariant scattering transform ${\overline{S}}f$.

Proof: Any $p^{\prime}\in{\mathcal{P}}_{J{+}1}$ can uniquely be written as an extension of a path $p\in{\mathcal{P}}_{J}$ where $p$ is the longest prefix of $p^{\prime}$ which belongs to ${\mathcal{P}}_{J}$, and $p^{\prime}=p+q$ for some $q\in{\mathcal{P}}_{J{+}1}$. The set of all extensions of $p\in{\mathcal{P}}_{J}$ in ${\mathcal{P}}_{J+1}$ is

It defines a non-intersecting partition of ${\mathcal{P}}_{J{+}1}=\cup_{p\in{\mathcal{P}}_{J}}{\mathcal{P}}^{p}_{J{+}1}$. We shall prove that such extensions are nonexpansive:

To later prove Proposition 3.3, we also verify that it preserves energy

Summing (40) on all $p\in{\mathcal{P}}_{J}$ proves (38).

Applying it to $g=U[p]f-U[p]h$ together with $U[p]f\star\phi_{2^{J}}=S_{J}[p]f$ and $U[p]f\star\psi_{2^{J}r}=U[p+2^{J}r]f$ gives

Since $S_{J{+}1}[{\mathcal{P}}_{J{+}1}]U[p+2^{J}r]f=\{S_{J{+}1}[p+2^{J}r+p^{\prime\prime}]\}_{p^{\prime\prime}\in{\mathcal{P}}_{J{+}1}}$, and $S_{J+1}[{\mathcal{P}}_{J{+}1}]f$ is nonexpansive, it implies

which proves (40). Since $S_{J}[{\mathcal{P}}_{J{+}1}]f$ preserves the norm, setting $h=0$ in (2.4) gives

This proposition proves that $\|S_{J}[{\mathcal{P}}_{J}]f-S_{J}[{\mathcal{P}}_{J}]h\|$ is positive and non-increasing when $J$ increases, and thus converges. Since $S_{J}[{\mathcal{P}}_{J}]$ is nonexpansive, the limit metric is also nonexpansive

For admissible scattering wavelets which satisfy (30), Theorem 2.6 proves that $\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$ so $\lim_{J\rightarrow\infty}\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$. The following theorem proves that the limit metric is translation invariant.

Proof: Since $S_{J}[{\mathcal{P}}_{J}]\,L_{c}=L_{c}\,S_{J}[{\mathcal{P}}_{J}]$ and $S_{J}[{\mathcal{P}}_{J}]f=A_{J}\,U[{\mathcal{P}}_{J}]f$

This lemma is proved in Appendix B. Applying it to $\tau=c$ and hence $\|\tau\|_{\infty}=|c|$ proves that

Since the admissibility condition (30) is satisfied, Lemma 2.8 proves in (37) that for $J>1$

If $\|f\|_{w}<\infty$ then it results from (46) that

so $\lim_{J\rightarrow\infty}\|L_{c}S_{J}[{\mathcal{P}}_{J}]f-S_{J}[{\mathcal{P}}_{J}]f\|=0$.

Letting $n$ go to $\infty$ proves that $\lim_{J\rightarrow\infty}\|L_{c}S_{J}[{\mathcal{P}}_{J}]f-S_{J}[{\mathcal{P}}_{J}]f\|=0$, which finishes the proof.$\Box$

5 Lipschitz Continuity to Actions of Diffeomorphisms

We denote ${\mathcal{P}}_{J,m}$ the subset of ${\mathcal{P}}_{J}$ of paths of length strictly smaller than $m$, and $(a\vee b)=\max(a,b)$.

Proof: Let $[S_{J}[{\mathcal{P}}_{J}],L_{\tau}]=S_{J}[{\mathcal{P}}_{J}]\,L_{\tau}-L_{\tau}\,S_{J}[{\mathcal{P}}_{J}]$,

Similarly to (43) the first term on the right satisfies

Since $S_{J}[{\mathcal{P}}_{J}]$ iterates on $U_{J}$ which is nonexpansive, Appendix D proves the following upper bound on scattering commutators.

Indeed, ${U_{J}}=M\,{W_{J}}$, where $M\{h_{J},(h_{\lambda})_{\lambda\in{\Lambda}_{J}}\}=\{h_{J},(|h_{\lambda}|)_{\lambda\in{\Lambda}_{J}}\}$ is a nonexpansive modulus operator. Since $ML_{\tau}=L_{\tau}M$

Inserting (55) with (56) and (54) in (52) gives

Lemma 2.11 proves that $\|L_{\tau}A_{J}-A_{J}\|\leq C\,2^{-J}\,{\|\tau\|_{\infty}}$. This inequality and (58) imply that

To prove (49), the main difficulty is to compute an upper bound of $\|[{W_{J}},L_{\tau}]\|$, and hence of $\|[{W_{J}},L_{\tau}]\|^{2}=\|[{W_{J}},L_{\tau}]^{*}\,[{W_{J}},L_{\tau}]\|$, where $A^{*}$ is the adjoint of an operator $A$. The wavelet commutator applied to $f$ is

The operator $[{W_{J}},L_{\tau}]^{*}\,[{W_{J}},L_{\tau}]$ has a singular kernel along the diagonal but Appendix E proves that its norm is bounded.

Inserting the wavelet commutator bound (61) in (59) proves the theorem inequality (49). One can verify that (49) remains valid when replacing ${\mathcal{P}}_{J}$ by the subset of paths of length smaller than $m$: ${\mathcal{P}}_{J,m}=\cup_{n<m}{\Lambda}_{J}^{n}$, if we replace $\|U[{\mathcal{P}}_{J}]f\|_{1}$ by $\|U[{\mathcal{P}}_{J,m}]f\|_{1}$. The inequality (51) results from

because $U[{\Lambda}_{J}^{n}]f$ is computed in (24) by applying the norm-preserving operator ${U_{J}}$ on $U[{\Lambda}_{J}^{n-1}]f$. $\Box$

The condition $\|\nabla\tau\|_{\infty}\leq 1/2$ can be replaced by $\|\nabla\tau\|_{\infty}<1$ if $C$ is replaced by $C\,(1-\|\nabla\tau\|_{\infty})^{-d}$. Indeed $\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$ and $\|S_{J}[{\mathcal{P}}_{J}]L_{\tau}f\|\leq\|f\|(1-\|\nabla\tau\|_{\infty})^{-d}$. This remark applies to all subsequent theorems where the condition $\|\nabla\tau\|_{\infty}\leq 1/2$ appears. The theorem proves that the distance $\|S_{J}[{\mathcal{P}}_{J}]L_{\tau}f-S_{J}[{\mathcal{P}}_{J}]f\|$ produced by the diffeomorphism action $L_{\tau}$ is bounded by a translation term proportional to $2^{-J}\|\tau\|_{\infty}$ and a deformation error proportional to $\|\nabla\tau\|_{\infty}$. This deformation term results from the wavelet transform commutator $[{W_{J}},L_{\tau}]$. The term $\log(\|\Delta\tau\|_{\infty}/\|\nabla\tau\|_{\infty})$ can also be replaced by $\max(J,1)$ in the proof of Theorem 2.12. For compactly supported functions $f$, Corollary 2.15 replaces this term by the log of the support radius.

The following corollary derives from Theorem 2.12 that a windowed scattering is Lipschitz continuous to the action of diffeomorphisms over compactly supported functions.

Similarly to Theorem 2.12, if ${\mathcal{P}}_{J}$ is replaced by the subset ${\mathcal{P}}_{J,m}$ of paths of length smaller than $m$, then $\|U[{\mathcal{P}}_{J}]f\|_{1}$ is replaced by $m\,\|f\|$ in (64). If $L_{\tau}f(x)=f((1-s)\,x)$ with $|\nabla\tau(x)|=|s|<1$ then the upper bound (64) is proportional to $m\,|s|\,\|f\|$. In this case, a lower bound is simply obtained by observing that since $\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$ and $\|S_{J}[{\mathcal{P}}_{J}]L_{\tau}f\|=\|L_{\tau}f\|=(1-s)^{-1}\,\|f\|$

Together with the upper bound (64), it proves that if $\tau(x)=sx$ then the scattering distance of $f$ and $L_{\tau}f$ is of the order of $\|\nabla\tau\|_{\infty}\,\|f\|$.

The next theorem reduces the translation error term $2^{-J}\|\tau\|_{\infty}$ in Theorem 2.12 to a second-order term $2^{-2J}\|\tau\|^{2}_{\infty}$, with first-order Taylor expansion of each $S_{J}[p]f$. We denote $\nabla S_{J}[{\mathcal{P}}_{J}]f(x)=\{\nabla S_{J}[p]f(x)\}_{p\in{\mathcal{P}}_{J}}$ and $\tau(x)\cdot\nabla S_{J}[{\mathcal{P}}_{J}]f(x)=\{\tau(x)\cdot\nabla S_{J}[p]f(x)\}_{p\in{\mathcal{P}}_{J}}$.

Proof: The proof proceeds as the proof of Theorem 2.12. Replacing $S_{J}[{\mathcal{P}}_{J}]L_{\tau}-S_{J}[{\mathcal{P}}_{J}]$ by $S_{J}[{\mathcal{P}}_{J}]L_{\tau}-S_{J}[{\mathcal{P}}_{J}]+\tau\,.\,\nabla{S_{J}}[{\mathcal{P}}_{J}]$ in the derivation steps of the proof of Theorem 2.12 amounts to replace $L_{\tau}A_{J}-A_{J}$ by $L_{\tau}A_{J}-A_{J}+\nabla A_{J}$. Equation (58) then becomes

Appendix C proves that there exists $C>0$ such that

Inserting the upper bound (61) of $\|[{W_{J}},L_{\tau}]\|$ proves (67). $\Box$

If $2^{J}\gg\|\tau\|_{\infty}$ and $\|\nabla\tau\|_{\infty}+\|{H}\tau\|_{\infty}\ll 1$ then $K(\tau)$ becomes negligible and $\tau(x)$ can be estimated at each $x$ by solving the system of linear equations resulting from (67):

In dimension $d$, the displacement $\tau(x)$ has $d$ coordinates which can be computed if the system (70) has rank $d$. Estimating $\tau(x)$ has many applications. In image processing, the displacement field $\tau(x)$ between two consecutive images of a video sequence is proportional to the optical flow velocity of image points.

Normalized Scattering Transform

A path $p\in{\mathcal{P}}_{J}$ can be extended into an infinite set of paths in ${\mathcal{P}}_{J{+}1}$ which refine $p$. In that sense, ${\mathcal{P}}_{J{+}1}$ is a set of higher resolution paths. When $J$ increases to $\infty$, these progressive extensions converge to paths of infinite length, which belong to an uncountable path set ${\overline{\mathcal{P}}_{\infty}}$. A measure and a metric are defined on ${\overline{\mathcal{P}}_{\infty}}$.

As elements of the topology, cylinder sets are open sets but are also closed. Indeed the complement of a cylinder set is a union of cylinders and is thus closed. As a result, the topology is a sigma algebra, on which a measure $\mu$ can be defined. The measure of a cylinder set $C$ is written $\mu(C)$.

This family of cylinder sets generates the same sigma algebra as open cylinders since open cylinders can be written $C_{n}(\lambda)=\cup_{(\lambda_{1},...,\lambda_{n})\in{\Lambda}_{\infty}^{n}}C(\lambda_{1},...,\lambda_{n},\lambda)$. The following proposition defines a measure on ${\Lambda}^{\infty}_{\infty}$ from the scattering of a Dirac:

There exists a unique $\sigma$-finite Borel measure $\mu$, called Dirac scattering measure, such that $\mu(C(p))=\|U[p]\delta\|^{2}$ for all $p\in{\mathcal{P}}_{\infty}$. For all $2^{l}g\in\Lambda_{\infty}$ and $p\in{\mathcal{P}}_{\infty}$, $\mu(C(2^{l}gp))=2^{dl}\mu(C(p))$ If $|\hat{\psi}(\omega)|+|\hat{\psi}(-\omega)|\neq 0$ almost everywhere then $\|U[p]\delta\|\neq 0$ for $p\in{\mathcal{P}}_{\infty}$.

Proof: The Dirac scattering measure is defined as a subdivision measure over the tree that generates all paths. Each finite path $p$ corresponds to a node of the subdivision tree. Its sons are the $\{p+\lambda\}_{\lambda\in{\Lambda}_{\infty}}$, and $C(p)=\cup_{\lambda\in{\Lambda}_{\infty}}C(p+\lambda)$ is a non-intersecting partition. Since

it results that $\mu(C(p))=\sum_{\lambda\in{\Lambda}_{\infty}}\mu(C(p+\lambda))$. The sigma additivity of the Dirac measure over all cylinder sets results from the tree structure, and the decomposition of the measure of a node $\mu(C(p))$ as a sum of the measures $\mu(C(p+\lambda))$ of all its sons. This subdivision measure is uniquely extended to the Borel sigma algebra through the sigma additivity. Since ${{\Lambda}_{\infty}^{\infty}}=\cup_{\lambda\in{\Lambda}_{\infty}}C(\lambda)$ and $\mu(C(\lambda))=\|U[\lambda]\delta\|^{2}=\|\psi_{\lambda}\|^{2}$, this measure is $\sigma$-finite.

We showed in (20) that $U[p](2^{l}g\circ f)=2^{l}g\circ U[2^{-l}gp]f$. Since $2^{l}g\circ\delta=2^{-dl}\delta$ it results $\|U[2^{-l}gp]\delta\|^{2}=2^{-dl}\|U[p]\delta\|^{2}$ and hence $\mu(C(2^{l}gp))=2^{dl}\mu(C(p))$.

A topology and a metric can now be constructed on the path set ${\Lambda}^{\infty}_{\infty}$. Neighborhoods are defined with cylinder sets of frequency resolution $2^{J}$:

If $p\in{\mathcal{P}}_{\infty}$ is a path of length $m$ then

Suppose that $|\hat{\psi}(\omega)|+|\hat{\psi}(-\omega)|\neq 0$ almost everywhere. For any $q\neq q^{\prime}\in{\overline{\mathcal{P}}_{\infty}}$

defines a distance on ${\overline{\mathcal{P}}_{\infty}}$, and ${\overline{\mathcal{P}}_{\infty}}$ is complete for this metric.

Since $U[p+\lambda]\delta=U[p]\delta\star\psi_{\lambda}$ and $|\hat{\phi}_{2^{J}}(\omega)|^{2}=\sum_{\lambda\in{\Lambda}_{\infty}\atop|\lambda|\leq 2^{-J}}|\hat{\psi}_{\lambda}(\omega)|^{2}$, the Plancherel formula implies

Since $S_{J}[p]\delta=U[p]\delta\star\phi_{2^{J}}$, Young’s inequality implies $\|S_{J}[p]\delta\|\leq\|U[p]\delta\|_{1}\,\|\phi_{2^{J}}\|$. Moreover $\|U[\lambda]f\|_{1}\leq\|\psi_{\lambda}\|_{1}\|f\|_{1}$ with $\|\psi_{\lambda}\|_{1}=\|\psi\|_{1}$, so we verify by induction that $\|U[p]\delta\|_{1}\leq\|\psi\|^{m}$. Inserting $\|\phi_{2^{J}}\|^{2}=2^{-dJ}\|\phi\|^{2}$ proves (72).

Let us now prove that $\bar{d}$ defines a distance. If $q\neq q^{\prime}$, we denote $\bar{p}\in{\mathcal{P}}_{\infty}$ their common prefix of longest size $m$, which may be , and show that $\bar{d}(q,q^{\prime})\neq 0$. Let $|q_{m+1}|=2^{j_{m+1}}$ and $|q^{\prime}_{m+1}|=2^{j^{\prime}_{m+1}}$ be the frequencies of their first different coordinate. If $2^{-J}=\max(|q_{m+1}|,|q^{\prime}_{m+1}|)$ then $(q,q^{\prime})\in C_{J}(\bar{p})^{2}$ and it is the smallest set including both paths so $\bar{d}(q,q^{\prime})=\mu(C_{J}(\bar{p}))$. It results that $\bar{d}(q,q^{\prime})\neq 0$ because $\mu(C_{J}(\bar{p}))\geq\mu(C(\bar{p}+2^{J}r))$ for $r\in{G}^{+}$ and Proposition 3.1 proves that $\mu(C(p))\neq 0$ for all $p\in{\mathcal{P}}_{\infty}$, so $\bar{d}(q,q^{\prime})\neq 0$.

The triangle inequality is proved by showing that

This is verified by writing $\bar{d}(q,q^{\prime})=\mu(C_{J}(\bar{p}))$, $\bar{d}(q^{\prime},q^{\prime\prime})=\mu(C_{J^{\prime}}(\bar{p}^{\prime}))$ and $\bar{d}(q^{\prime},q^{\prime\prime})=\mu(C_{J^{\prime\prime}}(\bar{p}^{\prime\prime}))$. Necessarily $\bar{p}$ is a substring of $\bar{p}^{\prime}$ or vice versa, and $\bar{p}^{\prime\prime}$ is larger then the smallest of the two. If $\bar{p}^{\prime\prime}$ is strictly larger then the smallest say $\bar{p}$, then $\mu(C_{J^{\prime\prime}}(\bar{p}^{\prime\prime}))\leq\mu(C(\bar{p}^{\prime\prime}))\leq C_{J}(\bar{p})$, so (74) is satisfied. If $\bar{p}^{\prime\prime}=\bar{p}=\bar{p}^{\prime}$ then $2^{-J^{\prime\prime}}\leq\max(2^{-J},2^{-J^{\prime}})$ and (74) is satisfied. Otherwise $\bar{p}^{\prime\prime}=\bar{p}$ is strictly smaller than $\bar{p}^{\prime}$ and necessarily $2^{J^{\prime\prime}}=2^{J}$ so (74) is also satisfied.

2 Scattering Convergence

It is a piecewise constant function of the path variable $q$, whose resolution increases with $J$. Since $\mu(C_{J}(p))=\|S_{J}[p]\delta\|^{2}$,

The following proposition proves that ${\overline{S}}_{J}$ is a nonexpansive operator which preserves the norm.

where ${\mathcal{P}}_{J{+}1}=\cup_{p\in{\mathcal{P}}_{J}}{\mathcal{P}}^{p}_{J{+}1}$ is a disjoint partition. Applying this to $f$ and $h$ implies

Summing over $p\in{\mathcal{P}}_{J}$ and inserting (77) proves (78).

Since \Big{|}\|S_{J}[p]f\|-\|S_{J}[p]h\|\Big{|}\leq\|S_{J}[p]f-S_{J}[p]h\|, summing this inequality over $p\in{\mathcal{P}}_{J}$ and inserting (77) proves the first inequality of (79). The second inequality is obtained because $S_{J}[{\mathcal{P}}_{J}]$ is nonexpansive. Setting $h=0$ proves that $\|{\overline{S}}_{J}\|_{\overline{\mathcal{P}}_{\infty}}=\|S_{J}[{\mathcal{P}}_{J}]f\|$ and Theorem 2.6 proves $\|S_{J}[{\mathcal{P}}_{J}]f\|=\|f\|$, which gives (80). $\Box$

Since $\|{\overline{S}}_{J}f-{\overline{S}}_{J}h\|_{\overline{\mathcal{P}}_{\infty}}$ is non-decreasing and bounded when $J$ increases, it converges to a limit which is smaller than the limit of the non-increasing sequence $\|S_{J}[{\mathcal{P}}_{J}]f-S_{J}[{\mathcal{P}}_{J}]h\|$. The following proposition proves that ${\overline{S}}_{J}f$ converges pointwise to the scattering transform on ${\mathcal{P}}_{\infty}$ introduced in Definition 2.3.

Proof: If $p\in{\mathcal{P}}_{\infty}$ then for $J$ sufficiently large ${\overline{S}}_{J}f(p)={\|S_{J}[p]f\|}/{\|S_{J}[p]\delta\|}$. Let us prove that

and that this equality also holds for $f=\delta$. Since $S_{J}[p]f=U[p]f\star\phi_{2^{J}}$, the Plancherel formula implies

Since $|\hat{\psi}(\omega)|+|\hat{\psi}(-\omega)|\neq 0$ almost everywhere, Proposition 3.1 proves that $U[p]\delta\neq 0$. Since it is positive, it has a non-zero integral. It results from (83) that $\lim_{J\rightarrow\infty}{\|S_{J}[p]f\|}/{\|S_{J}[p]\delta\|}=\int U[p]f(x)dx/\int U[p]\delta(x)dx$ which proves (82). $\Box$

The scattering transform ${\overline{S}}f$ can now be extended to ${\overline{\mathcal{P}}_{\infty}}$ as a windowed scattering limit:

then ${\overline{S}}_{J}f$ converges in norm to ${\overline{S}}f$ with $\|{\overline{S}}f\|_{\overline{\mathcal{P}}_{\infty}}=\|f\|$ and

Since ${\bf L}^{2}({\overline{\mathcal{P}}_{\infty}},d\mu)$ is complete, ${\overline{S}}_{J}f(q)$ converges in norm to its limit inf ${\overline{S}}f$. Since $\|{\overline{S}}_{J}f\|=\|f\|$, it also implies that $\|{\overline{S}}f\|_{\overline{\mathcal{P}}_{\infty}}=\|f\|$. Moreover, $U[p+q]=U[q]U[p]$ so $\|{\overline{S}}_{J}U[p]f\|_{\overline{\mathcal{P}}_{\infty}}^{2}=\int_{C(p)}|{\overline{S}}_{J}f(q)|^{2}\,d\mu(q)$. Since $\|{\overline{S}}_{J}U[p]f\|_{\overline{\mathcal{P}}_{\infty}}^{2}=\|U[p]f\|^{2}$ taking the limit when $J$ goes to $\infty$ proves (86).

The windowed scattering convergence (87) relies on the following lemma.

Since (85) implies that ${\overline{S}}_{J}f$ and ${\overline{S}}_{J}h$ respectively converge in norm to ${\overline{S}}f$ and ${\overline{S}}h$, the convergence (87) results from (88). Proving (88) is equivalent to proving that $\lim_{J\rightarrow\infty}\sum_{p\in{\mathcal{P}}_{J}}I_{J}(f,h)[p]=0$ for

When summing over $p\in{\mathcal{P}}_{J}$, we separate $\Omega_{J}^{f}\cup\Omega^{h}_{J}$ from its complement in ${\mathcal{P}}_{J}$. Since $\lim_{J\rightarrow\infty}\|{S_{J}[\Omega_{J}^{f}]f}\|^{2}=0$, $\|{S_{J}[{\mathcal{P}}_{J}]f}\|^{2}=\|f\|^{2}$, $\lim_{J\rightarrow\infty}\|{S_{J}[\Omega_{J}^{h}]h}\|^{2}=0$, and $\|{S_{J}[{\mathcal{P}}_{J}]h}\|^{2}=\|h\|^{2}$, dividing the sum over $\Omega_{J}^{f}$ and $\Omega_{J}^{h}$ and applying Cauchy-Schwartz proves that

and $\sum_{p\in{\mathcal{P}}_{J}}\|S_{J}[p]f\|\,\|S_{J}[p]h\|\leq\|f\|\,\|h\|$. The hypothesis (85) applied to $f$ and $h$ gives

so (3.2) implies that $\lim_{J\rightarrow\infty}\sum_{p\in{\mathcal{P}}_{J}}I_{J}(f,h)[p]=0$, which finishes the Lemma proof.

3 Numerical Comparisons with Fourier

In higher dimensions $d\geq 1$, this construction is extended as follow. All cylinders $C(\lambda)$ for all paths $p=\lambda=2^{j}r$ of length $1$ are mapped to non-intersecting hyper-rectangles $q^{-1}(C(\lambda))$ of measure