Convolutions in Image Processing | Week 1, lecture 6 | MIT 18.S191 Fall 2020

[@nickh2935]

congrats on getting literally the best teacher ever for this class

[@a_llama]

@rikdeb banerjee what?

[@sayanjitb]

@rikdeb banerjee what 🤔?

[@AdityaGhosh50]

@rikdeb banerjee what?

[@AnubhavGoswami3800]

@rikdeb banerjee what?

[@vstillliving5850]

@rikdeb banerjee what?

[@passerby4507]

If I were the students, I would be so freaked out about the professor sounding like that moving pi on the interwebz.

[@52.yusrilihsanadinatanegar79]

BTW, it's 3Blue1Brown.

[@Derpuwolf]

Yusril Atfan I have a feeling they know

[@barkli2978]

Yusril Atfan nah its papa flammy

[@AlexandruJalea]

Me is confused 🤣 ze pi creatures has been replaced by the miau creatures

[@ca-ke9493]

i'm 3 weeks behind on my actual lectures, but 3b1b has tricked me into watching a half an hr lecture that has nothing to do with my degree

[@aditi_05]

Saame

[@nullpointer1755]

Me too, i'm studying Biomedicine on my university but i find this lectures so interesting

[@cheponis]

I suspect, that is NOT by accident..... ;-)

[@JanBabiuchHall]

How did you know I was supposed to be learning circuit analysis right now

[@saverussnape]

approves

[@sumitgupta6905]

I am a simple man, I see 3blue1 brown I click.

[@nothingspecial7399]

Ikr

[@brunomartel4639]

hahhahahhhhaa dude

[@maaan8494]

nohomo

[@lilapela]

2word4syllable

[@damnguen1726]

me too

[@DipietroGuido]

Wtf imagine having him as your actual professor

[@yendar9262]

Don't do that man, don't give me hope

[@vinamarora7049]

Isn't he our 'actual' professor now too? I mean he just delivered us a lecture full of actual information.

[@DipietroGuido]

@@vinamarora7049 he is, he just doesn't grade us

[@portlyoldman]

The future of education is men like Grant Sanderson and his ilk 😎

[@ThunderAppeal]

Youre an idiot

[@quahntasy]

*Wish Universities would hire faculty like Grant instead of PowerPoint slide readers that we got*

[@chizhang2765]

I really don't think it matters that we get active researchers to teach the first two years of the undergrad physics/maths, but the way universities in general work now you'll most usually have to be a good researcher to be given a teaching post.

[@halian.vilela]

The moment you finally realize what was that "gaussian blur" filter you've seen in Photoshop since forever!

[@LuisAlonzoRivero]

Teachers that are also content creators is the future of online learning. The quality of this course was off the charts.

[@Thomas.P.C]

AAAA I was so jealous when one of my MIT friends said they got Grant Sanderson to be teaching. MIT is super lucky to have you! Feel free to teach at Caltech too though ;-;

[@MahmoudAyman0]

first world problems!

[@keshavkasat9465]

@@MahmoudAyman0 lol...true. at least we can access these recordings

[@MahmoudAyman0]

@@keshavkasat9465 not mentioned the under qualified professors we have at my school

[@cheponis]

MIT grad here. Cal-tech? What is that? Some UC football team?

[@Thomas.P.C]

@@MahmoudAyman0 yea... I wish I could say you're wrong.

[@ijeremyoliver]

19:47 "This will really accentuate the points where this Sobel filter, convolved across the image, ends up non-zero." I love that moment in a lecture where the professor says something that 20 minutes early would have been absolute nonsense to me.

[@HighestRank]

Then wait 20 minutes before reading my next sentence. *earlier

[@xintongbian]

20:41 how he just explained the whole idea of convolution neural network in just 3 seconds ...

[@nollix]

This actually made me kind of pissed at how badly most things are explained. Imagine all the other super complicated-sounding things that are actually reasonable to understand, but you're missing out on them for this reason. Just take a look at the Wikipedia article and how full of junk it is. Why can't everything be explained like Grant does it? Christ. It's like most people don't actually understand anything/the high level concepts behind most things, and have to wave their hands and throw lingo at you to cover it up.

[@love_joy_minimalist]

well, to be fair he was able to do that because he spent the first 20 mins talking about what a kernel is

[@KurohiNeko]

@@love_joy_minimalist Yeah it makes a lot more sense in context, but even so I'm amazed by this person

[@fragdeinpferd]

@@nollix same at our university. I even delayed to watch and learn our lecturer's videos because they piss me off every time I try to concentrate on them. The contrast couldn't be bigger. This video was awesome and managed to explain things in a way that you get an intuitive understanding, whereas in the lecture, we are thrown at with mathematical terms which hinder me from taking up the essential information :D I am very grateful for being able to watch this video.

[@enisten]

15:46 So, what was the correct answer here? "C. Sharpen" appears at the top with 143 clicks. "B. Detect edges" is marked green. But Grant says, "So, looks like most people thought that it would detect edges. But if we actually play with this . . . the effect that it has on the picture of the cat here is that actually it kind of sharpens it up . . . Now, for those of you who did answer 'edge detecting,' you definitely are on the right track." So, is it that most people actually were right to say "C. Sharpen" and Grant mistakenly marked "B. Detect edges" as the correct answer of the poll and then thought green means the most number of clicks?

[@xKhfan213x]

Yes, sharpen was the correct term. He said edge detection was wrong but didn't select the correct answer, he kinda just jumps back to the notebook to explain why it's sharpen and not edge detection Edit... If you look at the 3 x 3 array, when you have the positive number in the center surrounded by all negatives, which was the multiple choice, your going to be sharpening the image in some form where as the edge detection array is split up into negatives in the first column, zeros in the second and positive in the third.

[@3blue1brown]

My mistake! The correct answer was "sharpen", but I evidently had not set the correct answer correctly ahead of time. Most people gave the correct answer, but all I saw in the moment was that the green bar was number 2.

[@SDoylerrs]

I can't believe this is a live stream. It's so well planned and executed. Can't wait for next week.

[@lafasanagnuhd4098]

I don't think Grant is gonna see this but still... I am so glad to see a teachter who is so passionated about teaching the world and sharing his knowledge. If you happen to read this, thank you so much!!! u helped me so much for understanding mathmatical concepts for my engineering bachelor

[@hamsterpoop]

15:45 The correct answer is "Sharpen" not "Detect Edges". This technique is called "Unsharp Masking". Also the answer to the question in 14:38 is "Yes, but...", it's called "deconvolution". It can work but, as you correctly mentioned, up until a certain point that depends on how accurately you know the convolutional function and whether there is any other noise in the problem.

[@nostradingus3237]

Mr. Sanderson; thank you. I am deeply appreciative of your ability to intuitively explain these oft challenging concepts, and your willingness to do it so prolifically and on an open platform, and I’m sure that this sentiment is near universal for anyone who tunes in!

[@therainman7777]

I see that you’re in your “walking thesaurus” phase. I would strongly suggest just using regular language and typing the same way you talk (and hopefully you don’t talk like this).

[@riley530]

@@therainman7777 agreed

[@guikich]

You can think the image as an Electrical signal. As you apply the Fourier Transform you get the frequencies in the "signal" (Image). As you make the convolution again on the Fourier version, you are actually returning to the "pixels" domain and Filtering the image, which get rids of higher spacial frequencies.

[@fragdeinpferd]

kudos for that comment, you just answered an open question I yet had to find an answer for :D

[@SSJProgramming]

14:42 This is a very good question and having done work in Super Resolution (a field that attempts to find solutions to that problem, for the application of improving spatial resolution) I can give some quick details. This will be in the context of images taken from cameras. 1) Yes you're losing information so recovering the original information perfectly using NOTHING but the blurry image is practically impossible because of noise amplification, unknown kernels used for convolution, all sorts of non constant, non symmetric kernels. Its even possible that many different images when blurred can give the same blurred output which makes picking a particular solution completely arbitrary. 2) Nevertheless, we can augment the problem in a few different ways, one of which is to add new sources of information that represent the original image in some way. This can be done with dictionary lookups, non local means methods, AI based restoration, etc. Other methods like iterative deconvolution RL deconvolution / weiner deconvolution, and artificial high frequency amplification give estimates for the original image, and in most cases actually look pretty good. However, it is also possible to introduce information contamination that can lead to false objects, such as when you amplify high frequency components that are corrupted by noise leading to artifacts (like ringing) and other phantom objects. Any kind of prior knowledge about the image such as context, kernel used in convolution can all aid in the restoration process. The field is pretty rich, but the best methods to date are the AI based methods -> there are some videos from "Two minute papers" that shows the results of AI based methods, completely beating out (non AI based) methods that I developed as well. I posted them here for whoever is interested in this kind of work. kzbin.info/www/bejne/g6immKmPqbR_iZI kzbin.info/www/bejne/fqerYZVvgMR8qNE Anyways, great video, keep up the good content!

[@abc3631]

This guy can't be appreciated enough. There are so many minute nuances to his videos that really make a big difference when you add all up. His dedication to make the content as intuitive as possible is awe inspiring. God bless him

[@vierikristianto1334]

Watching this has taken 36 minutes of my time in the most pleasant way I can imagine

[@beautyofsylence]

Well I guess I'm going to learn Julia now 😂

[@ArrowRaider]

I was intrigued by Julia in the past and now this is a sign from the KZbin algorithm gods that it is time to learn it.

[@dragosmanailoiu9544]

BAHAHAHA

[@haibai1766]

@@ArrowRaider yeah I randomly came across it in something comparing major programming languages, and they happened to mention Julia (Don't remember what or where it was though), so I looked into it a bit, but didn't really do much. Thanks for the initiative Professor Grant!

[@nullpointer1755]

I would love to se a series about audio processing as well, and how to use the FFT in that context.

[@rohitathithya3964]

hi! have you found any interesting videos or lectures?

[@Hiyori___]

Acoustic engineering student here. So glad I've found this video... it's amazing to see convolution applied to images. Makes the concept much more clear and intuitive. Superb lecture

[@DrunkenUFOPilot]

I can imagine a video explaining convolution using audio, but most people don't spend much time studying audio on oscilloscopes or analyzing reverb with their ears. Visual is so much more natural and obvious.

[@H14m]

I thought I was watching a class that had have nothing to do with what I should actually learn for my degree, and he suddenly makes me understand kernels, which was actually a topic I needed to learn. Thank you!!

[@fburton8]

It isn't possible to reconstruct the original image from the blurred one. Grant had it spot on about information being lost. There are theoretically infinite (or practically many) ways to get the same blurred pixel value by summing the pixel values covered by the kernel. A perfect deconvolution would require the original values to be assigned back to the pixels that they came from, information which isn't stored in convolved output.

[@stpirate89]

I think you're right. It would have been interesting to see what the sharpen kernel did after the image had been blurred. I'm now also intrigued as to what sharpening an image then blurring it would do...

[@fburton8]

@@stpirate89 That would be interesting to try!

[@iverbrnstad791]

@@stpirate89 I think it could make it a bit more cartoonish, sharp but possibly with less detail.

[@jambor3]

If you have the kernel though, shouldn't you be able to do the deconvolution (maybe modulo some artifact from the fourier transform)? More concretely, can't you take the blurred image, transform to fourier space, divide by the fourier space kernel, and inverse fourier transform the result back to get the original image (I guess maybe to within a constant offset)?

[@arejaybee]

lol got a notification for 3 blues and a brown. Amazing channel for anyone who enjoys his teaching style. Enjoyed learning convolutions again!

[@djimmyriodan7280]

4 days ago i was looking for image processing by 3b1b i was dissapointed not to find any ....and now youtube suggested this .. published in 3 september 1 day after my search ... what are the odds ... i love it thank you very much sir you are the best

[@olegborisov5091]

I m just wondering why other lecturers don’t share this crystal clear perspectives, it feels that they don’t fully understand the reasons behind all the operations themselves...

[@akaHarvesteR]

Teaching is a talent and a skill, and this man is the epitome of excellence in teaching.

[@Wander4P]

I feel like I understand how a lot of common photo editing effects work now.

[@Xammed]

I had to learn Julia a year ago! Now the best teacher on the planet is teaching it.

[@distrologic2925]

"It's a literal edge case!" I don't know why I found that so funny :D

[@ichisadashioko]

Grant Sanderson's videos on the Julia channel have views than most other videos combined.

[@llxArthurll]

I just wanted my ead classes to be like this, what a quality class

[@amarug]

for the question about "can you recover the original from the blurred one" its easiest to imagine the Fourier transform of the image convolved with the gaussian: there the frequency spectrum will be "elementwise" multiplied with a gaussian, which will clip off high frequencies, so the information is truly lost and can't be recovered. it's really like taking and out of focus image. apart from some "illusions" like reverse diffusion or "guessing" by a neural net, the true information can't be recovered...

[@hamsterpoop]

This is incorrect. The information can be recovered through deconvolution but making some assumptions about the "blurring" filter. This is commonly done in Astronomy and Geophysics. In practice (i.e. in the presence of noise and uncertainty about the cause of the blur), the recovery is not 100% perfect, so it's a partial recovery.

[@amarug]

@@hamsterpoop Incorrect. What is lost is lost. You can try to guesstimate some of the lost high frequency data to create the illusion of it being there and some methods also do a pretty decent job to make it look believable to the human eye, but you can never retrieve what is lost.

[@roderik1990]

14:41 you can indeed recover the original from a blurred image. Such deconvolution even has established uses in image restoration, and astronomy. That said there's limitations and between noise, nonlinearities, the kernel and the method used, data can get lost.

[@nafrost2787]

I'm guessing the way to recover the original from the convolution is essentially working backwards from the averages to find original values by solving the corresponding linear equations?

[@vinceb8041]

Grant Sanderson is the patron saint of visual math teaching

[@erikgrundy]

After seeing what the Laplace/Fourier transforms can do to electrical circuits, I maybe shouldn't be surprised at the other wonders it can do, but seeing it pop up here as well is fascinating.

[@HornWilliam]

I've been studying this topic a while now. I've used this in many of my works. This visualization has finally made me get it. Thanks a lot 3b1b :D

[@deepaks.m.6709]

Happy Teacher's day Grant! It's so sweet of you to spend your life to empower the future of our world. 😇🙂

[@DrunkenUFOPilot]

"Is it possible to reconstruct the original from the blurred image?" Yes, I did that for a living for a major NASA mission. Basic principle is to divide the Fourier transform of the image by the Fourier transform of the kernel. Result is the Fourier transform of a good estimate of the original image.

[@kristianTV1974]

Wish I'd had this guy lecturing when I majored in signal processing.

[@Darthvanger]

"30 min is such a short time for a lecture" - the guy who explained linear algebra in 45 min better than a semester in university.

[@fastundercoverkitgoogle7381]

Wait, whaaaat? I'm watching an MIT class on convolutions given by Grant(3b1b) and posted on Julia's youtube channel? I certainly didn't expect that

[@jknair0]

the visualization and depth of teaching is amazing

[@zym9785]

I would love to see this same lecture with another hour or so added on to it... or maybe a part 2? Amazing lecture btw.

[@InvaderMik]

9:58 When I was being trained in data visualization, using green and red within the same plot was considered something of a faux pas. I think it had to do with the relative prevalence of red-green colorblindness.

[@Florian-ps1qv]

yeah because red/ green would only see gray. I think its smth thats very easy to forget as I didnt think about it either. Nice of you to point this out

[@yubai6549]

Restoring image from blur is a classic research direction for several decades

[@jadynancz]

Literally an amazing explainer

[@syntheticsandwich190]

I’m not even taking this class, but by just listening I’ve learned a lot. Cool video.

[@prasmi23]

21:42 Niravana...by far the only person who has correctly explained the inversion, which is the crucial bit...a bit that people tend to forget,overlook or not learn when coming from 1D to 2D convolution...i have happy:)

[@shiladitya7739]

MIT must feel grateful that they got Grant.

[@ebeb9156]

Explanation about diff between sharp filter and edge detector blow my jaw out! We as students literlly day before had crazy debate about it with two image procc doctors. And they couldnt answered us what diff. Omg.... listen man, thoose doctors are experts in Deep Learning.... What it makes you Grandt Sanderson? The Mesaiah 😇🙌🙌🙌🙌

[@Yasharvl]

Thanks Grant, it's a pleasure to have you here!

[@codekomali1760]

Congratulations to MIT and The Julia Programming Language!

[@portlyoldman]

Those man is a legend. After decades 3Blue1Brown finally got me understanding Div and Curl 😁

[@sakshidwivedi4754]

I got so happy seeing him, I almost cried 🥺

[@alan2here]

The Wolfram language deconvolution is really impressive. :)

[@HectorLopez-ue4qb]

Grant Sanderson is the absolute best teacher

[@sophiophile]

15:00 If you know what the original convolution function was for a gray-scale image (at least), since you know that the surrounding pixels had the same convolution applied, you can deconvolve an image. It's really really computationally intensive (used to wait hours to deconvolve image slices from a 3-d raster scan), but it's done regularly in fluorescence microscopy, where the original 'convolution' (as defined by a point-spread function) is calculated from calibration of your setup (or you just fall back on certain presets).

[@gingervytis]

I worked as a budding software engineer in the MIT/Harvard community for 18 months in the mid-90s. A wonderful life-changing experience.

[@govindbarwa1806]

That should have been quite amazing sir. I just want to know the approach, one should take to navigate a path in today's coding era. Should one focus quantitatively or qualitatively and if qualitatively then how should one increase the quality if one wants to perhaps. It would be pretty great if you would share us some of your insights.

[@sankalpachowdhury7378]

this is going to be an outstanding content on julia, I'm blessed to have subscribed this channel earlier. ❤️ Julia

[@FFT3D]

The answer to the question asked at 14:42 is yes. The process is called Deconvolution. It involves finding the kernel. An image I, is equal to, k * RI, which is the convolution (denoted *) of the real image (RI) with the kernel, k. If you have just the image, I (in the case of the question, a blurred image), then one needs the kernel that caused the blurring in order to remove it. The process is done using Fourier transforms. One could recover the image, ReI, as following, ReI = F(I)/F(k), where F(x) is Fourier transform of the function x. Note, in real life, the recovered image will be a bit off (ReI - RI is not equal to 0) due to the inaccuracy of the reconstructed kernel. Finding the kernel that one assumes their image has been convolved with is another door in the field of physics and math. The first-order approximation is the point spread function.

[@BomberTVx]

I was confused on why 3b1b was there lol

[@samwinnick4048]

Great video! For those wondering about the question of inverting the convolution by a given kernel, consider the following: (1) How might you do it (using an algorithm you probably learned in high school) in the case of a 1 dimensional image? (2) The ring of polynomials in n variables is not a Euclidean domain for n>1...

[@samwinnick4048]

(Too late to edit): I should have also mentioned that this is obviously not the end of the story. The more important point, as mentioned in the video, is that you can use a convolutional neural network to try to learn a kernel to perform tasks such as deblurring images with predictable features. Just thought it might also be interesting to some folks to point out this connection to ring theory.

[@Toschi23]

Came here for Julia stayed for Grant Sanderson

[@beketmyrzanov1979]

OMG! This guy is lit. I am going to pray for you 5 times a day. Please keep creating content

[@Gameboygenius]

Go check out the 3blue1brown channel. If you haven't seen it yet, you're in for a treat.

[@patrykkrzyzanski2159]

Congrats man, you are doing great, nice to see you as an MIT ....

[@prometheus7387]

Damn, Grant is making MIT courses approachable to a high school student like myself.

[@joseluismatabuenasedano6881]

now than I having online classes at university I am realizing even morehow good he is. Amazing videos here.

[@guikich]

3blue1 brown this act of filtering the spacial frequencies is what a set of lens (space->frequency domain) + aperture (cut out high frequencies) + lens ( frequency domain -> space) do .

[@ca-ke9493]

Could you explain more? This is interesting

[@guikich]

@@ca-ke9493 www.rp-photonics.com/fourier_optics.html "By placing an optical aperture in a Fourier plane, one can effectively modulate the spatial frequency spectrum. For example, with a circular aperture centered on the optical axis, one can implement a low-pass filter, transmitting only components with sufficiently low spatial frequencies. (That is the operation principle of some mode cleaners.) With a second lens, one can transform back into real space."

[@guitoo1918]

14:34 Convolution is reversible as long as the spectrum of the kernel doesn't have zeros. The edges would be feathered though because we dont compute outside the frame.

[@justinwhite2725]

20:41 I'm here for convolutional neural networks but I'm fascinated by this. I always wondered how those filters in image manipulation software worked and now I know how to do it myself if it ever became practical.

[@TheAIEpiphany]

Really nice way to introduce convolutions! Start with (visual) examples, slowly build up intuition and then start digging into the maths (if needed).

[@BananthahallyVijay]

What a brilliant, smooth flowing lec. Could get a quick idea of the concepts I had always wanted to know about. 10/10.

[@lktyagi88]

You can really change the world understand mathematics. Amazing job!

[@evenaicantfigurethisout]

28:27. Several differences worth noting. 1. With the image were not adding together terms in the polynomial. 2. The (single) Fourier series describes the entire image, whereas the analogy present here might lead one to think that the terms in the series corresponds to the pixels one after another.

[@newperspective5918]

Wow 25:00 bind blown, thanks for teaching me that!

[@TheZenytram]

Maaannnn this is so gooood, I'm completely illiterate on image processing subject, but i could follow every step and actually understand this lesson, Grant is so fucking good at teaching, he should make a course to teach processional in their respective areas how to teach clearly to anyone.

[@emmanuelkoutsoudakis4614]

Kudos for excellent series.

[@samyu4473]

Smart guys can teach very clearly and make you understand easily. Funny that I can understand MIT lectures but not my own lecture...

[@ResilientFighter]

This professor is awesome!!! So happy to see Julia taking off

[@Wonders_of_Reality]

Love your new design! It’s so much easier to read black text on a white background!

[@gravylake8394]

It's worth remembering that when taking RGB values from an image they are usually stored in gamma space so as to be perceptually linear instead of actually linear. To apply a convolution kernel correctly the values must be linearized first, then converted back to gamma space after. Minute Physics has a great video on this called Computer Color is Broken.

[@anassheashaey]

I saw Grant in the thumbnail and Julia language in the title and I thought the youtube app has a bug.

[@dennisestenson7820]

14:38, nowadays there are inverse convolutions, and diffusion models, which effectively do just that.

[@professionalprocrastinator8103]

Convoluting an image with a gaussian kernel when it comes to image processing (blurring) is analogous to applying a diffusion operator to the image. In physics, diffusion is known as an irreversible phenomenon. This has something to do with entropy naturally evolving towards a maximum from the point of view of thermodynamics - or diffusion being an exergonic process; you'd have to bring in free energy to reverse the effect, through a non-spontaneous process that takes in free energy from the surroundings (which many believe is why life can be sustained). Anyway, the diffusion equation (commonly known as heat equation) has a time-dependent term and the diffusion operator. By replacing t by -t in the equation, it becomes clear why diffusion is irreversible from a mathematical standpoint.

[@Tupster]

It really looks to me like in the Mario example you are convolving the already convolved image instead of creating a new one because it gets more and more blurry as you go from the top left to the bottom right. In fact, I think the discussion of scanning the image in a particular order is misleading because all of the computed points in the convolution can be done simultaneously because it isn't a "running average" or anything like that. The convolution function computes a single point at a time independently so it can be done in a random order.

[@dannyisrael]

you can unblur an image if you store the edge information (edge_info = original_image - blurred_image), then you could add that back in, which isn't exactly what was asked, but had to do something like that on an assignment in the past.

[@parthasarathis349]

Grant I love the way you explain things in an easier way.

[@KurohiNeko]

Its really interesting if you connect 26:08 with your Taylor Series video on approximating functions by taking derivatives to get the coefficients of a polynomial that approximates said function. If we consider 2 functions and we approximate them with these polynomials (for a domain), and then we can convolve the functions by convolving their polynomial approximation's coefficients.

[@mariamhasany5740]

Superb explanations! Thanks for such a nice and easy to understand lecture

[@benhbr]

15:00 you can in Theory recover a function from its convolution, but only if you have infinite precision. The rounding errors make the original unrecoverable in practice.

[@deinauge7894]

at the end he answered the question if the blurring is reversible: it is indeed, because in fourier space you can just devide by the transformed kernel and get the original back ;-) but be careful with edge effects...

[@prowhiskey2678]

This lecture is so well prepared, well done!

[@donaldhobson8873]

Many kernels, like Gaussian, can be produced by first doing a horizontal convolution, and then a vertical. If that still isn't fast enough, there is a trick to speed the convolution up further. Suppose you have an N dimensional function space that is invarient under translation. For example, the space of all polynomials of degree at most N-1. This forms a vector space, as if f(x) and g(x) are polynomials of degree at most N-1, then a*f(x)+b*g(x) is too. Also if f(x) is in this space, so is g(x)=f(x+c). Another example would be sin and cosine waves of a finite set of fixed frequencies. Suppose the function you want to do a 1d convolve with is in such a space. Pick a basis of that space. f_1(x) .. f_N(x) Pointwise multiply each function in the basis with the array. So if A is the array to convolve, calculate the array [ A[1]*f_i(1) , A[2]*f_i(2) ... ] for each i in range 1 to N. Then take the running sum of each array. You can now find the sum of A[j]*f_i(j) over an arbitrary interval, just by taking the difference between the endpoints. But any function in your function space, is a linear combination of these. Putting this all together, you can convolve any array with any section of any polynomial, with a runtime that scales like length(array)*degree(polynomial). If the function you want to convolve with is piecewise polynomial, that would multiply the runtime by the number of pieces. EDIT: I now think that this algorithm is quadratic in the degree of polynomial. You need to calculate which linear combination of convolutions with the f_i(x)'s to use. This doesn't depend on A, so if you are convolving multiple 1d arrays by the same polynomial, these values could be cached. The fastest way I can see to do this is to write f_i(x+1) as a linear combination of f_j(x)'s then put these values in a matrix (over all i,j) Then take the vector that is the linear combination of f_i(x)'s that you want to convolve with, and repeatedly multiply it by the matrix.

[@informativt]

On reconstruction of a blurred image, that's called "compressed sensing" which is, or was, a very hard problem. You might know the consequence of that research as deep neural networks

[@RaviranjanKumar-ny1re]

Your way of explaining topics really amazing sir, thank you so much for such an interesting tutorial 🙏

[@vil9386]

Grant Sanderson is god for me! Thank you!

[@JudahDaniels]

This was fantastic, can't wait for the next one!

[@hugueds]

best video about conv ever, you are a god in any subject!