# Matrix convolution **URL:** \ **Category:** Community Support\ **Tags:** kdb-and-q\ **Created:** [October 18, 2020, 9:35pm UTC](https://forum.kx.com/t/matrix-convolution/12077 "2020-10-18T21:35:00Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![DevonMcC1](https://avatars.discourse-cdn.com/v4/letter/d/f9ae1b/32.png) [@DevonMcC1](https://forum.kx.com/u/DevonMcC1)\ **Post date:** [October 18, 2020, 9:35pm UTC](https://forum.kx.com/t/matrix-convolution/12077/1 "2020-10-18T21:35:00Z")
Hi - I’m trying to figure out how to do a convolution on a matrix applied to successive overlapping sub-windows. Say I have a larger matrix   q)m4:zpad 4 4#“f”$til 16 where zpad:{0,/:flip 0,/:(flip x,:0),:0} / pad w/0s all around and a smaller convolution matrix to apply to all 3x3 sub-windows within m4: q)m0:3 3#-1 -1 -1 -1 8 -1 -1 -1 -1 So I want to convolve m0 against each of these sub-window in m4: ±--------±----------±----------±--------+ |0 0 0 |0 0 0 |0 0 0 |0 0 0 | |0 0 1f |0 1f 2f |1f 2f 3f |2f 3f 0 | |0 4f 5f |4f 5f 6f |5f 6f 7f |6f 7f 0 | ±--------±----------±----------±--------+ |0 0 1f |0 1f 2f |1f 2f 3f | 2f 3f 0| |0 4f 5f |4f 5f 6f |5f 6f 7f | 6f 7f 0| |0 8f 9f |8f 9f 10f |9f 10f 11f |10f 11f 0| ±--------±----------±----------±--------+ |0 4f 5f| 4f 5f 6f| 5f 6f 7f| 6f 7f 0| |0 8f 9f| 8f 9f 10f| 9f 10f 11f|10f 11f 0| |0 12f 13f|12f 13f 14f|13f 14f 15f|14f 15f 0| ±--------±----------±----------±--------+ |0 8f 9f| 8f 9f 10f| 9f 10f 11f|10f 11f 0| |0 12f 13f|12f 13f 14f|13f 14f 15f|14f 15f 0| |0 0 0 | 0 0 0 | 0 0 0 | 0 0 0| ±--------±----------±----------±--------+ I’m thinking that since m4 is a list of lists, maybe I need to generate the set of indexes into m4, like this: q)m4[0 1 2;0 1 2] 0 0 0 0 0f 1f 0 4f 5f q)m4[0 1 2;1 2 3] 0 0 0 0 1 2 4 5 6 and so on for 16 sets, or use an iterator but have not come up with anything non-loopy. Does anyone have any suggestions? Thanks, Devon – Devon McCormick, CFA Quantitative Consultant ---
**Author:** ![DevonMcC1](https://avatars.discourse-cdn.com/v4/letter/d/f9ae1b/32.png) [@DevonMcC1](https://forum.kx.com/u/DevonMcC1)\ **Post date:** [October 19, 2020, 2:28am UTC](https://forum.kx.com/t/matrix-convolution/12077/2 "2020-10-19T02:28:00Z")
Here’s what I came up with.  It’s not too elegant and it assumes both matrixes are square and that the convolution matrix is 3x3 (because we pad the target matrix with one row and column of zeros on each side): q)m0:3 3#-1 -1 -1 -1 8 -1 -1 -1 -1 / Edge detector convolver q)zpad:{0,/:flip 0,/:(flip x,:0),:0} / Pad mat all around w/1 row & col of 0s on each side q)m4:zpad 4 4#“f”$til 16 / Mat to convolute q)shape:{(count x),count x[0]} / Shape of regular rectangular array q)convo:{[x;y] sum raze x_y} / 1D convolution q)n0:count m0 q)n1:count m4 q)n2:(count m4)-n0-1 q)sd1:raze (n1_til n0)+:til n0 q)idxm4:((n2_n2),n0_n0)#raze (raze flip sd1+:n1\*til n2)+/:til n2 q)flip (n2,n2)#((raze m4) idxm4)convo: raze m0 The last line performs the convolution, giving the expected answer of  -10 -9 -6 9 9 0 0 24 21 0 0 36 66 51 54 85 This works by building the indexes into m4 of each sub-window into a 16x9 matrix and convoluting each row against raze m0.  Any suggestions for improvement are welcome. Thanks, Devon ---
**Author:** ![TerryLynch1](https://avatars.discourse-cdn.com/v4/letter/t/9e8a1a/32.png) [@TerryLynch1](https://forum.kx.com/u/TerryLynch1)\ **Post date:** [October 20, 2020, 11:06am UTC](https://forum.kx.com/t/matrix-convolution/12077/3 "2020-10-20T11:06:00Z")
I suspect there isn’t anything wrong with your approach - you flatten the matrices and deal with the flattened indices which is a good idea. Here’s an approach that doesn’t flatten but indexes at depth, it should also handle non-square matrices.  q)f:{til[1+count-c]+:til c:count y}; q){count[a 0]cut(sum raze y\*)@/:x ./:raze a:fx;y/::f[x 0;y 0]}[m4;m0] -10 -9 -6 9 9 0 0 24 21 0 0 36 66 51 54 85 Terry ---
**Author:** ![User7](https://avatars.discourse-cdn.com/v4/letter/u/7ea924/32.png) [@User7](https://forum.kx.com/u/User7)\ **Post date:** [October 20, 2020, 12:03pm UTC](https://forum.kx.com/t/matrix-convolution/12077/4 "2020-10-20T12:03:00Z")
Convolutions are expensive operations, O(n^2),  it’s going to be hard to be much faster If you are working with larger convolutions I would consider instead implementing the convolution as a multiplication in the Fourier domain (i.e., FFT each matrix, multiple and inverse back) which can drop complexity to O(n log n). Implementing this in kdb borrowing from the Kx whitepaper on Signal Processing, this would require padding your matrices to a power of 2  so you need to consider the benefits.  ---
**Author:** ![DevonMcC1](https://avatars.discourse-cdn.com/v4/letter/d/f9ae1b/32.png) [@DevonMcC1](https://forum.kx.com/u/DevonMcC1)\ **Post date:** [October 24, 2020, 11:32pm UTC](https://forum.kx.com/t/matrix-convolution/12077/5 "2020-10-24T23:32:00Z")
Thanks for the help.  I may look at the Fourier transform if what I have is too slow but I want to complete the process all the way to the end before I worry about optimizing it.  Does anyone have something for reading JPGs or PNGs into q?  I have a kluge for now but it would be more seamless if I could read images directly. ---
**Author:** ![rocuinneagain1](https://avatars.discourse-cdn.com/v4/letter/r/fbc32d/32.png) [@rocuinneagain1](https://forum.kx.com/u/rocuinneagain1)\ **Post date:** [October 27, 2020, 4:37pm UTC](https://forum.kx.com/t/matrix-convolution/12077/6 "2020-10-27T16:37:00Z")
Hi Devon, .pgm and .ppm files have a very easy to parse format. You can make a system call to imagemagik which will convert your jpg/png: pixels:`short$@[;4] system"convert file.jpg pgm:-" https://imagemagick.org/script/command-line-processing.php#output This code has many flaws but may still be of interest: https://github.com/rianoc/qCam Rian ---
**Author:** ![noravale168](https://avatars.discourse-cdn.com/v4/letter/n/ecae2f/32.png) [@noravale168](https://forum.kx.com/u/noravale168)\ **Post date:** [October 12, 2026, 9:12am UTC](https://forum.kx.com/t/matrix-convolution/12077/7 "2026-10-12T09:12:36Z")
Late addition for anyone who finds this thread while searching for image-processing style convolutions in q. An alternative that avoids building the index matrix is to iterate over the kernel offsets instead of over the sub-windows. For a c×c kernel there are only c² offsets, and for each offset you can take a shifted n×n slice of the padded matrix in one indexing operation, multiply it by the scalar kernel weight, and sum the resulting matrices: ```auto conv:{[k;m] c:count k; / kernel size n:1+count[m]-c; / output size sum {[k;m;n;ij] k[ij 0;ij 1]*m[ij[0]+til n;ij[1]+til n]}[k;m;n] each til[c] cross til c } q)conv[m0;m4] ``` Because `sum` on a list of equal-shaped matrices adds them element-wise, this gives the same 4×4 result as the version above, and it works for any square kernel size without changing the padding logic (pad by `c div 2` on each side for "same" output). Strictly speaking this is cross-correlation; for symmetric kernels like the Laplacian edge detector m0 it is identical to convolution, otherwise reverse the kernel first with `reverse each reverse k`. The vectorised form also scales much better on real images: the work is c² whole-array multiplications, which q handles efficiently, rather than one small dot product per pixel. The same pattern covers blur (box or Gaussian kernels), sharpening and Sobel gradients, so it is a handy building block if you are preprocessing image data stored as matrices in kdb+. Classical kernels like these are the foundation that modern learned models build on: convolutional networks stack many trained kernels, and current [image to image ai](https://imgtoimg-ai.com/) editors use deep generative models to restyle or restore a whole photo while keeping its composition. For deterministic, explainable filters on numeric data, though, a small kernel loop like the one above is usually all you need.