Convolution from the Constraint

A convolutional layer applies the same small filter at every position of its input. That is usually introduced as a design choice, a clever way to save parameters that happens to work well on images. In this post we derive it instead. We write down what it means for a linear layer to respect translations, treat that as an equation for the weights, and solve it. Convolution comes out as the only solution. That constraint, and what it forces on a layer, is also what much of equivariant deep learning is about: solving it for other groups and representations, and analyzing what happens when a layer deviates from it.

Once the problem is stated in terms of group representations, the same few lines also give the Fourier picture of the layer, and a recipe that works for rotations, spheres and other groups too. We'll do it on the simplest domain that has a symmetry, the circle. The figure on the right follows the text. You can also step it yourself with the buttons under it, or with ← and →.

A signal on the circle

Take a periodic signal, a function f : S¹ → ℝ on the circle, and sample it at N equally spaced points x_k = 2𝜋k/N, here with N = 16. A network never gets the curve itself. It gets these sixteen numbers, and they are the entire input. The two dashed lines mark the ends of the plot, which are the same point on the circle.

Now stand the plot on its side, so that sample k sits at the height of entry k, and the samples become a column vector f ∈ ℝ¹⁶. Nothing changed but the drawing. From here on the row reads from right to left, in the direction the algebra runs. Something is lost though. To the linear algebra f is just a list. That entry 3 is the neighbor of entry 4, and entry 15 the neighbor of entry 0, is something we know and the vector does not.

Representations

The symmetry of the circle is rotation. The rotations that map sample points onto sample points are the multiples of 2𝜋/N, and they form the cyclic group C_N ⊂ SO(2). It is generated by one element g, the rotation by one sample, and g^m rotates by m samples.

To let the group act on our vectors we need a representation. That is a map 𝜌 : G → GL(V) that assigns to every group element an invertible matrix acting on a vector space V, such that

In other words, a representation is a group homomorphism from G into the invertible matrices. Composing two group elements and then taking the matrix is the same as multiplying their matrices. One group has many representations, on spaces of different sizes, and we'll need two of them.

Example one: the regular representation

Rotating the signal moves its values along,

and on the vector that is a permutation matrix 𝜌(g^m), with ones on a shifted diagonal and in the corner where the signal wraps. Shift by one sample, by two, by five. Each step multiplies in one more copy of 𝜌(g), and what leaves at the bottom comes back at the top, which is the circle again.

These matrices compose the way the rotations do, 𝜌(g)𝜌(h) = 𝜌(gh), so this is a representation, and it has a name. The sample points form a single orbit of the group, so once we pick x₀ as base point, every sample is labelled by the group element that takes x₀ there. The signal is then a function on the group itself, f : C_N → ℝ, and the group acts on it by moving the argument,

A group acting on functions on itself is the regular representation. It is the one the data comes with, and everything below starts from it.

Changing basis

So far the signal is written in the sample basis, one basis vector per sample point, the way an image is written in pixels. Nothing forces that choice. We might as well describe the same signal relative to a basis of sines and cosines. On the circle that is the Fourier series,

with a₀ the mean. On the sixteen samples the series becomes a matrix. Put the sampled basis functions in the rows of a matrix Q. Multiplying by it takes the inner product of the signal with each basis function, which gives the coefficients,

Each row is normalized, so Q is orthogonal and Q⁻¹ = Q^T, whose columns are the same basis functions, so the signal is a combination of them. The figure shows the transform f̂ = Q f and draws each basis function as a curve over its own row, the constant on top, then cosine and sine pairs of increasing frequency, and the fastest wave (−1)ⁿ at the bottom. The coefficients f̂ are sixteen numbers again, the same signal in other coordinates. This smooth signal has most of its weight in the first few frequencies.

Example two: the Fourier representation

The group acts in this space too. If the samples transform as f ↦ 𝜌(g) f, then the coefficients transform as f̂ ↦ Q 𝜌(g) Q⁻¹ f̂, and conjugating by Q keeps products intact, so this is again a representation. It is block diagonal,

with R(𝜃) the 2 × 2 rotation matrix,

The panel under the figure writes out one block at a time, the one for l = 1, framed in the matrix, or l = 3, which turns three times as fast. You know this as the Fourier shift theorem. Shift a signal by an angle 𝛼 and every frequency keeps its amplitude while its phase moves: the pair (a_l, b_l) of f(x − 𝛼) is the pair of f rotated by l𝛼. On the samples 𝛼 = 2𝜋m/N, and the angle is 𝜃_l m. Step g, and again, and on to half a turn. Each block turns at its own frequency, the lowest one slowest, the constant never moves, and the last one only flips sign. In the plots each cosine and sine pair sits in a dashed box as wide as its amplitude √(a_l² + b_l²). A shift moves weight between the two stems of a pair, one grows as the other shrinks, but it never changes the box. The outer plots are the signals themselves: on the right f = Q⁻¹ f̂, on the left the rotated coefficients transformed back, Q⁻¹ ŷ = 𝜌(g^m) f, which is the shifted signal. In complex form the same theorem reads f̂_l ↦ e^−il𝛼 f̂_l.

The regular and the Fourier representation are equivalent, the same action written in two bases. What the Fourier basis adds is that the action falls apart into small pieces that each act on their own. A representation is irreducible when no subspace other than zero and the whole space is mapped to itself by every 𝜌(g). The blocks here are irreducible over the reals, since a rotation by 𝜃_l maps no line in the plane to itself, and they are the irreps of C_N. Over the complex numbers each rotation block splits once more into e^±i𝜃_lm, and we get sixteen one-dimensional irreps, each appearing once.

This is not special to the circle. That every representation of a finite group splits into irreps is Maschke's theorem. For the regular representation of a compact group the Peter–Weyl theorem says more. L²(G) decomposes into all irreps of G, over the complex numbers each appearing as many times as its dimension, and the change of basis that does it is the Fourier transform on G. For SO(2) that is the Fourier series we started from, so the shift theorem is Peter–Weyl for the circle. On the sphere the spherical harmonics play the same role.

The figure draws this for C₁₆. The permutation on the left is the product of three matrices, the basis change Q⁻¹ with the waves down its columns, the irrep blocks, and Q with the same waves along its rows. Step g a few times and only the permutation and the blocks change. The two basis changes do not depend on g at all.

A linear layer

Put a learnable layer in the operator slot, y = W f, with W any 16 × 16 matrix. That is N² = 256 free parameters. Every output entry is a weighted sum of all the input entries, and for a generic W the output has no visible relation to the shape of the input.

The question we care about is what happens when the input is rotated first. Does the output rotate with it? We want W 𝜌(g) f to be equal to 𝜌(g) W f. The wide ghost curve on the left is 𝜌(g) y, the output rotated after the fact, and the solid curve is what the layer gives for the rotated input. At the identity they agree for free. One sample is enough to make them unrelated. The input barely moves and the output changes completely.

There is a second way to ask the same question, and it leads straight to the constraint. Rotate the input, apply the layer, and then rotate the output back,

This is the layer seen from a rotated frame. We move the signal, process it, and move the result back, as if the signal had never been shifted. If the layer respects the rotation, y″ should be exactly the output for the unshifted input, W f, drawn as the ghost. One sample or five, and for this W what comes back is something else entirely.

The constraint

Asking for this for every input and every group element is the equivariance constraint,

The second form is the rotated frame from above, with the three matrices multiplied out into one. The figure shows both sides. On the right is 𝜌(g)⁻¹ W 𝜌(g), the same weights read from shifted rows and shifted columns. The constraint says the two grids are the same picture. For one shift or for five, for a learned W they are not even close. At the identity the constraint asks nothing.

The constraint is linear in W, so its solutions form a linear subspace, and we can just solve it. Two observations make this short. Since 𝜌(g^m) = 𝜌(g)^m, it is enough to impose it for the generator g, and the rest follows. And written out entry by entry, 𝜌(g)⁻¹ W 𝜌(g) is W with both indices moved on by one. So the constraint reads

Every entry has to equal its neighbor down and to the right, all the way around. W is constant along its wrapped diagonals, so it is fixed by a single column, W_nk = w_n−k, and

That is a convolution. The solutions form a space of dimension N, sixteen numbers instead of 256, and every one of them is a convolution. So weight sharing is what the constraint forces on the layer. In group notation the same formula reads y(g) = ∑_h w(h⁻¹g) f(h), the group convolution, and in that form the derivation goes through for any group.

The figure finds its solution by averaging over the group,

Conjugating W̄ by any 𝜌(h) only reorders the sum, so W̄ satisfies the constraint, and it is the solution closest to W: the average is the orthogonal projection onto the solution space. Once it has settled, step g a few times and the two grids stay equal.

Back to the signal

Put the solved layer back in the rotated frame, now with a short kernel, w_d nonzero only for |d| ≤ 2. Shift by one, by five, and y″ lands exactly on the ghost every time. The sliders under the figure set the five taps, and every setting passes, because every w solves the constraint. So a linear layer on the circle is equivariant if and only if it is a convolution. The constraint has no other solutions, and every convolution satisfies it. The short support is a second choice, locality, which equivariance does not ask for. Equivariance alone allows all sixteen diagonals.

Written as a sum over the diagonals, W = ∑_d w_d 𝜌(g)^d. The layer is a weighted sum of the representation matrices themselves, and it is the form we need at the end.

Now look at what a single output is made of. Output 4 is computed by row 4 of W, and that row only has weights on inputs 2 to 6, the neighbors of sample 4. Output 10 is computed by row 10, which reads inputs 8 to 12 with the same five weights, moved six places along. Every row is the row above it moved one step to the right, so every output applies the same local filter to its own neighborhood. At the edge the window wraps around, because the signal lives on a circle.

This is why the convolution is equivariant. Shift the input by m, and the neighborhood that output j used to see now sits around j + m. Row j + m reads it with the same weights, so the same number comes out, m places further along. It works because the rows are shifted copies of one another, and a generic W fails the test because its rows are not.

Schur's lemma

Now go back to the Fourier basis and write the layer there. We had W = ∑_d w_d 𝜌(g)^d, and every 𝜌(g)^d has the same block form in the Fourier basis, so W does too,

Every frequency is processed on its own, by a rotation times a scale, which is the convolution theorem. The general reason is Schur's lemma, which says what an equivariant linear map can do between irreps. Between two irreps that are not equivalent it has to be zero, so frequencies never mix. From an irrep to itself it has to commute with the irrep, which for a rotation block leaves a rotation times a scale, and over the complex numbers a single scalar, ŷ_l = ŵ_l f̂_l. The count agrees too, 1 + 7·2 + 1 = 16, the same sixteen numbers as the circulant matrix, because it is the same layer in another basis. Change the kernel and the blocks change with it, but nothing appears off the blocks. A symmetric kernel has b_l = 0, and the layer is diagonal.

The main outcome

If we want a layer to preserve the group structure of its input, we have to constrain it. A linear layer is equivariant if and only if it is a group convolution, and the condition it has to satisfy is W = 𝜌(g)⁻¹ W 𝜌(g) for every g. A large part of equivariant deep learning in recent years consists of solving this constraint for various groups and representations, and, more recently, of analyzing how far a layer deviates from it when the symmetry in the data is only approximate.

The symmetries of the platonic solids

From here on we look at the symmetries of the platonic solids, and we want our layers to be equivariant to those. There are five regular solids, and the rotations that map each one onto itself form a finite subgroup of SO(3). The cube and the octahedron are duals and share a group, as do the dodecahedron and the icosahedron, so five solids give three groups: the tetrahedral group with 12 rotations, the octahedral with 24, and the icosahedral with 60.

Other finite groups

Nothing in the argument was special to the circle. Every finite group acts on functions on itself by permuting their values, so its regular representation is a permutation representation, exactly like the shift. On the left is the cyclic group C₁₂, acting on a 12-gon, and on the right the twelve rotations of a tetrahedron. Both permutation matrices have one 1 per row and column. For C₁₂ it is the shifted diagonal we have seen all along. For the tetrahedral group the pattern is scattered, because that group does not commute. The figure steps through all twelve elements. The constraint, its solution as a group convolution W_g,h = w(h⁻¹g), and the decomposition into irreps work the same way for both.

Platonic transformers

The same machinery is what the Platonic Transformer is built on. A standard transformer on a point cloud treats every point as a token with a feature vector, and attention updates those features using the positions of the other points. Those positions are written in one frame, so attention looks at the cloud from one point of view. Each point gets one feature, and if the cloud rotates, what it sees changes, and so do the features.

So we let attention look from every point of view the group allows. A point of view is a reference frame R, and the features computed from it depend only on the neighbors' positions relative to that frame, R⁻¹(x_j − x_i). Going around the cloud through all twelve rotations of the tetrahedral group, every point collects twelve features, one per frame. That is a function on the group at every point, f_i(R), the kind of signal the whole post has been about.

If the cloud itself is rotated by one of these rotations, the twelve points of view are the same twelve, relabeled, so every point's twelve features are permuted, not changed. To keep that structure through the network, every linear layer has to respect the permutation, and so it is a group convolution over the group, the constraint this post derived. The network then keeps reasoning in relative positions and relative orientations, this feature at this orientation, that feature at that one. The paper uses the rotation groups of the platonic solids, with 12, 24 or 60 elements.

The recipe

Nothing in the derivation used much about C_N beyond it being a group acting on the domain. In general the steps are the same. Write down the representations 𝜌_in and 𝜌_out that the input and output carry, solve W 𝜌_in(g) = 𝜌_out(g) W, and if you want the solution in its simplest form, change to the irrep basis, where Schur's lemma makes it block diagonal.

For signals on the sphere under rotations SO(3), each degree l of the spherical harmonics appears once, so a linear equivariant map from the sphere to itself is one number per degree. For the regular representation of a non-commutative group the irreps have dimension larger than one and appear several times, and then the blocks are small matrices that mix the copies of an irrep. The argument is the one above. The general version, for any group, is in lecture 1.7 of the GEDL course, and the irreps and the Fourier transform in lecture 2.3.