{"id":9299,"date":"2020-08-12T08:58:27","date_gmt":"2020-08-12T08:58:27","guid":{"rendered":"https:\/\/www.experfy.com\/blog\/?p=9299"},"modified":"2023-11-21T11:13:49","modified_gmt":"2023-11-21T11:13:49","slug":"deriving-convolution-from-first-principles","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/deriving-convolution-from-first-principles\/","title":{"rendered":"Deriving Convolution From First Principles"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Basics Of Deep Learning<\/em><\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

TL;DR:<\/strong>\u00a0Have you even wondered what is so special about convolution? In this post, I derive the convolution from first principles and show that it naturally emerges from translational symmetry.<\/em><\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n
\n

La connoissance de certains principes suppl\u00e9e facilement \u00e0 la connoissance de certains faits. (Claude Adrien Helv\u00e9tius)<\/p>\n<\/blockquote>\n\n\n\n

During my undergraduate studies, which I did in Electrical Engineering at the Technion in Israel, I was always appalled that such an important concept as convolution [1] just landed out of nowhere. This seemingly arbitrary definition disturbed the otherwise beautiful picture of the signal processing world like a grain of sand in one\u2019s eye. How nice would it be to have the convolution emerge from first principles rather than have it postulated! As I will show in this post, such first principles are the notion of translational invariance or symmetry.<\/p>\n\n\n\n

Let me start with the formula taught in basic signal processing courses defining the discrete convolution [2] of two\u00a0n<\/em>-dimensional vectors\u00a0x<\/strong>\u00a0and\u00a0w<\/strong>:<\/p>\n\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

Here, for convenience, I assume that all the indices run from zero to\u00a0n<\/em>\u22121 and are modulo\u00a0n<\/em>; it is convenient to think of vectors as defined on a circle. Writing the above formula as a matrix-vector multiplication leads to a very special matrix that is called\u00a0circulant<\/em>:<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t“Deriving Convolution From First Principles” \n
Illustration of shift equivariance as the interchangeability of shift and blur operations.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Another important fact taught in signal processing courses is the connection between the convolution and the Fourier transform [8]. Here as well, the Fourier transform lands out of the blue, and then one is shown that it diagonalises the convolution operation, allowing to perform convolution of two vectors in the frequency domain as element-wise product of their Fourier transforms. Nobody ever explains where these sines and cosines come from and what is so special about them.<\/p>\n\n\n\n

In order to get to the bottom of it, recall a fact from linear algebra:<\/p>\n\n\n\n

\n

Commuting matrices are jointly diagonalisable.<\/p>\n<\/blockquote>\n\n\n\n

In other words, two matrices satisfying\u00a0AB<\/strong>=BA<\/strong>\u00a0will have the same eigenvectors (but possibly different eigenvalues) [9]. Since all circulant matrices commute, we can pick one of them and compute its eigenvectors \u2014 the above theorem assures that these will be the eigenvectors of all circulant matrices as well.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

It is convenient to pick the shift operator\u00a0S<\/strong>. Since\u00a0S<\/strong>\u00a0is orthogonal matrix, we expect its eigenvectors to be orthogonal [10]. A simple calculation (see Section 4.1 in [5]) leads to the conclusions that<\/p>\n\n\n\n

\n

Shift operator is diagonalised by the Fourier transform.<\/p>\n<\/blockquote>\n\n\n\n

I hope that at this point you have your second \u201caha\u201d moment for today: this is where the sines and cosines come from! They are the eigenvectors of the shift operator; I denote them as columns of the matrix\u00a0\u03a6<\/strong>. Note that the eigenvectors are complex, so we need to take complex conjugation when transposing\u00a0\u03a6<\/strong>. Multiplication (from the left) by\u00a0\u03a6*<\/strong>\u00a0is called the Fourier transform, and by\u00a0\u03a6<\/strong>\u00a0the inverse Fourier transform.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t“Deriving Convolution From First Principles”\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

Since all circulant matrices are jointly diagonalisable, they are also diagonalised by the Fourier transform [11]. They differ only in their eigenvalues. The last missing bit is the realisation that<\/p>\n\n\n\n

\n

The eigenvalues of C(w<\/em><\/strong>) are the Fourier transform of w.<\/p>\n<\/blockquote>\n\n\n\n

We can now put all the pieces of the puzzle into a statement known as the\u00a0Convolution Theorem<\/a>: the convolution\u00a0x<\/strong>\u2217w<\/strong>\u00a0can be computed either as a circulant matrix\u00a0C<\/strong>(w<\/strong>) applied to\u00a0x<\/strong>\u00a0in the original system of coordinate (sometimes this is called \u201cspatial domain\u201d convolution), or in the Fourier basis (\u201cspectral domain\u201d) by first computing the Fourier transform of\u00a0\u03a6*x<\/strong>, multiplying it by the Fourier transform of\u00a0w<\/strong>\u00a0[12], and then computing the inverse Fourier transform.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t

\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t“Deriving Convolution From First Principles”\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

Because\u00a0\u03a6\u00a0<\/strong>has a special redundant structure, the products\u00a0\u03a6*x<\/strong>\u00a0and\u00a0\u03a6x\u00a0<\/strong>can be computed with \ud835\udcaa(n\u00a0<\/em>log\u00a0n<\/em>) complexity using a\u00a0Fast Fourier Transform<\/a>\u00a0(FFT) algorithm.<\/p>\n\n\n\n

Why is such a definition of convolution a big deal and should be taught this way? I will repeat here the quote from Helv\u00e9tius I opened this post with: \u201cThe knowledge of certain principles easily compensates the lack of knowledge of certain facts\u201d. In the case of convolution, its derivation from first principles allow easy generalisation to other domains. In a next post, I will show how to define convolution on graphs, in order to produce a key building block of graph deep learning<\/a> architectures.<\/p>\n\n\n

\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

[1] A. Dominquez-Torres,\u00a0The history and origins of convolution<\/a>\u00a0provides a fascinating excursion into the\u00a0historical development<\/a>\u00a0of the concept and notation of the convolution operation. The convolution integral shows up for the first time in a derivation of Taylor\u2019s theorem in J. B. D\u2019Alembert, Recherches sur diff\u00e9rents points importants du syst\u00e8me du monde (1754). The priority is often mistakenly attributed to P.-S. de Laplace, M\u00e9moire sur l\u2019inclinaison moyenne des orbites des com\u00e8tes, sur la figure de la terre et sur les fonctions (1773). M\u00e9moires de l\u2019Acad\u00e9mie Royale des Sciences de Paris, Savants \u00c9trangers 7:503\u2013540, though this publication contains no trace of convolution.\u00a0Laplace<\/a>\u00a0indeed used the convolution in his later memoir on probability, written in 1778 and published in 1781. Early naming attempts included\u00a0r\u00e9sultante<\/em>\u00a0(French for \u201cresultant\u201d, first used by Charles Cailler in 1899),\u00a0composizione<\/em>\u00a0(Italian for \u201ccomposition\u201d, by Vito Volterra in 1910), and\u00a0faltung<\/em>\u00a0(literally meaning \u201cfolding\u201d in German, by Gustav Doetsch in 1923); the latter term dominated the German literature in the beginning of the 20th century. The English name\u00a0convolution<\/em>\u00a0comes from the Latin\u00a0con<\/em>\u00a0(\u201ctogether\u201d) and\u00a0volvere<\/em>\u00a0(\u201croll up\u201d) and is a literal translation of the German\u00a0faltung,\u00a0<\/em>and so is the Russian variant\u00a0\u0441\u0432\u0451\u0440\u0442\u043a\u0430<\/em>. The first use of the English term can be traced to the 1934 paper of Aurel Friedrich Wintner; it was later cemented in the literature by authoritative works of Doetsch (1937) and Gardner and Barnes (1942). The star symbol was first used by Volterra in 1910, though in a different form. Percy John Daniel used a dot notation. The first modern notation of convolution as\u00a0f<\/em>\u2217g<\/em>, a combination of the two, is due to Doetsch (1923).<\/p>\n\n\n\n

[2] Technically speaking, what I define here is\u00a0circular convolution<\/em>.<\/p>\n\n\n\n

[3] Note that the rows of\u00a0C<\/strong>(w<\/strong>) have the vector\u00a0w<\/strong>\u00a0transposed, resulting in the reflection that appears in the convolution formula and distinguished it from a related notion of\u00a0correlation<\/a>. Pay attention to the boundary conditions (the elements of\u00a0C<\/strong>\u00a0in the top right and bottom left corners).<\/p>\n\n\n\n

[4] I use the terms\u00a0operator<\/em>\u00a0and\u00a0matrix<\/em>\u00a0interchangeably.<\/p>\n\n\n\n

[5] B. Bamieh,\u00a0Discovering transforms: a tutorial on circulant matrices, circular convolution, and the discrete Fourier transform<\/a>\u00a0(2018). arXiv:1805.05533 provides the details of the derivations I discuss in this post.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t

\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\n

[6] Some often confuse\u00a0invariance<\/em>\u00a0(meaning \u201cunchanged\u201d in Latin) and\u00a0equivariance<\/em>\u00a0(\u201cchanging in the same way\u201d), with many signal processing books referring to the property I discuss here as \u201cshift invariance\u201d. A function is\u00a0shift equivariant\u00a0<\/em>if\u00a0f<\/em>(Sx<\/strong>)=S<\/strong>f<\/em>(x<\/strong>).<\/em>\u00a0In other words, it does not matter whether we first apply the shift and then\u00a0f<\/em>\u00a0or vice versa. Differently, shift invariance is the property of being unaffected by shift: the function\u00a0f<\/em>(Sx<\/strong>)=f<\/em>(x<\/strong>) is\u00a0shift invariant<\/em>. Shift invariance is a fundamental concept in physics (where it often appears under the name of \u201ctranslational symmetry\u201d), stating that the laws of physics do not depend on the location in space. In variational formulation of classical mechanics, such a fundamental law as the conservation of momentum follows from shift invariance by virtue of\u00a0Noether\u2019s theorem<\/a>.<\/p>\n\n\n\n

[7] The concept of equivariance is more general and can be extended using the group theory formalism. This framework was used in T. Cohen and M. Welling,\u00a0Group equivariant convolutional networks\u00a0<\/a>(2016). Proc. ICML, to extend the shift equivariance of convolutional layers of CNNs to more general operations such as rotations. Assuming\u00a0f\u00a0<\/em>: X\u2192Y, where X and Y are some different spaces with corresponding groups \ud835\udca2 and \ud835\udca2\u2019 of operations defined on the elements of X and Y respectively, group equivariance is expressed as\u00a0f<\/em>(\ud835\udd24(x<\/strong>))=\ud835\udd24\u2019(f<\/em>(x<\/strong>)) where \ud835\udd24\u2208\ud835\udca2 and \ud835\udd24\u2019\u2208\ud835\udca2\u2019. Note that \ud835\udd24\u2019 is not necessarily equal to \ud835\udd24 as the structure and even dimension of the output space Y can be different from that of the input X. The standard convolution discussed in this post is a particular case with X=Y being the space of\u00a0n<\/em>-dimensional vectors, \ud835\udca2=\ud835\udca2\u2019 the translation group, and \ud835\udd24=\ud835\udd24\u2019 the shift operator.<\/p>\n\n\n\n

[8] Since we deal with finite-dimensional vectors, the term \u201cFourier transform\u201d refers here to the\u00a0Discrete Fourier Transform<\/a>\u00a0(DFT).<\/p>\n\n\n\n

[9] More precisely, joint diagonalisation implies that two commuting matrices have the same\u00a0eigenspaces<\/em>, as in the general case the eigenvalues can have non-trivial multiplicity. Since in the case I discuss here all the eigenvalues are simple, we can talk about a common eigenbasis.<\/p>\n\n\n\n

[10] However, since\u00a0S<\/strong>\u00a0is non-symmetric, it does not have real eigenvalues (symmetric real matrices have real eigenvalues). The eigenvalues of\u00a0S<\/strong>\u00a0happen to be the complex\u00a0roots of unity<\/a>.<\/p>\n\n\n\n

[11] When I say that matrix\u00a0C<\/strong>\u00a0is \u201cdiagonalised\u201d by the Fourier transform, I mean that the matrix\u00a0\u03a6*C\u03a6\u00a0<\/strong>is diagonal. Since Fourier transform is an orthogonal matrix (\u03a6*\u03a6<\/strong>=I<\/strong>), geometrically it acts as a change of the system of coordinates that amounts to an\u00a0n<\/em>-dimensional rotation. In this system of coordinates, the action of\u00a0C<\/strong>\u00a0becomes element-wise product.<\/p>\n\n\n\n

[12] In signal processing, one typically designs the filter in the frequency domain, so the Fourier transform of\u00a0w<\/strong>\u00a0is never explicitly computed.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"

Have you even wondered what is so special about convolution? Know how to derive the convolution from first principles and show that it naturally emerges from translational symmetry.<\/p>\n","protected":false},"author":874,"featured_media":9300,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[183],"tags":[544,543,206],"ppma_author":[3686],"class_list":["post-9299","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ai-ml","tag-convolution","tag-convolutional-newral-net","tag-deep-learning"],"authors":[{"term_id":3686,"user_id":874,"is_guest":0,"slug":"michael-bronstein","display_name":"Michael Bronstein","avatar_url":"https:\/\/www.experfy.com\/blog\/wp-content\/uploads\/2020\/08\/Michael-Bronstein-150x150.jpg","user_url":"https:\/\/www.imperial.ac.uk\/people\/m.bronstein","last_name":"Bronstein","first_name":"Michael","job_title":"","description":"Michael Bronstein is Professor, Chair in Machine Learning and Pattern Recognition at Imperial College, London, besides Head of Graph ML at Twitter \/ ML Lead at ProjectCETI\/ ex Founder & Chief Scientist at Fabula_ai\/ ex at Intel #AI #ML #graphs. His main expertise is in theoretical and computational geometric methods for data analysis, and his research encompasses a broad spectrum of applications ranging from machine learning, computer vision, and pattern recognition to geometry processing, computer graphics, and imaging. He has authored over 150 papers, the book Numerical geometry of non-rigid shapes (Springer 2008), and holds over 30 granted patents."}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/9299","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/874"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=9299"}],"version-history":[{"count":5,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/9299\/revisions"}],"predecessor-version":[{"id":34215,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/9299\/revisions\/34215"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/9300"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=9299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=9299"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=9299"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=9299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}