Signal Processing - July 2017 - 29

Rediscovering Standard CNNs Using Correlation Kernels
In situations where the graph is constructed from the data,
a straightforward choice of the edge weights (S9) of the
graph is the covariance of the data Let F denote the input
data distribution and
R = E (F - EF) (F - EF) <

(S13)

be the data covariance matrix. If each point has the same
variance v ii = v 2, then diagonal operators on the
Laplacian simply scale the principal components of F.
In natural images, because their distribution is approximately stationary, the covariance matrix has a circulant
structure v ij . v i - j and is thus diagonalized by the
standard discrete cosine transform (DCT) basis. It
follows that the principal components of F roughly correspond to the DCT basis vectors ordered by frequency.
Moreover, natural images exhibit a power spectrum
2
-2
E ft ^~h ~ ~ , because nearby pixels are more correlated than faraway pixels [14]. It results that principal
components of the covariance are essentially ordered
from low to high frequencies, which is consistent with
the standard group structure of the Fourier basis. When
applied to natural images represented as graphs with
weights defined by the covariance, the SCNN construction recovers the standard CNN, without any prior
knowledge [76] (Figure S5). Indeed, the linear operators
UC l, l l U < in (27) are by the previous argument diagonal

The previous discussion also applies to graphs instead of
manifolds, where one only has to replace the inner product in
(24) and (26) with the discrete one (16). All of the sums over
i would become finite, as the graph Laplacian matrix T has n
eigenvectors. In matrix-vector notation, the generalized convolution f * g can be expressed as Gf = U diag (gt ) U < f , where
gt = (gt 1, f, gt n) is the spectral representation of the filter,
and U = (z 1, f, z n) denotes the Laplacian eigenvectors (S8).
The lack of shift invariance results in the absence of circulant
(Toeplitz) structure in the matrix G, which characterizes the
Euclidean setting. Furthermore, it is easy to see that the convolution operation commutes with the Laplacian, GTf = TGf.

in the Fourier basis, hence translation invariant, hence
classical convolutions. Furthermore, the "Spectrum-Free
Methods" section explains how spatial subsampling can
also be obtained via dropping the last part of the spectrum of the Laplacian, leading to pooling, and ultimately
to standard CNNs.

(b)

(a)

FIGURE S5. The 2-D embedding of pixels in 16 × 16 image patches
using a Euclidean radial basis function (RBF) kernel. The RBF kernel is
constructed as in (S9), by using the covariance v ij as Euclidean distance between two features. The pixels are embedded in a 2-D space
using the first two eigenvectors of the resulting graph Laplacian. The
colors in (a) and (b) represent the horizontal and vertical coordinates
of the pixels, respectively. The spatial arrangement of pixels is roughly
recovered from correlation measurements.

Domain
Basis
Signal

X

X

f
(a)

Γ
(b)

Y
Tf

Γ

Tf

(c)

Uniqueness and stability
Finally, it is important to note that the Laplacian eigenfunctions
are not uniquely defined. To start with, they are defined up to
sign, i.e., D (! z) = m (! z) . Thus, even isometric domains
might have different Laplacian eigenfunctions. Furthermore, if
a Laplacian eigenvalue has multiplicity, then the associated
eigenfunctions can be defined as orthonormal basis spanning
the corresponding eigensubspace (or said differently, the eigenfunctions are defined up to an orthogonal transformation in the

FIGURE 2. A toy example illustrating the difficulty of generalizing spectral
filtering across non-Euclidean domains. (a) A function defined on a manifold (function values are represented by color). (b) The result of the application of an edge-detection filter in the frequency domain. (c) The same
filter applied on the same function but on a different (nearly isometric)
domain produces a completely different result. The reason for this
behavior is that the Fourier basis is domain dependent and the filter
coefficients learned on one domain cannot be applied to another one
in a straightforward manner.

IEEE SIGNAL PROCESSING MAGAZINE

|

July 2017

|

29
Table of Contents for the Digital Edition of Signal Processing - July 2017
