How do I determine if a matrix is contained in another matrix?

Question

Is there a clever way of determining if one matrix is contained within another larger matrix? Iterating over the larger matrix to check each item until potential matches show up is straightforward but gets slow for large matrices.

Example, a smaller matrix:

$$\begin{pmatrix}4&3&2\\2&3&4\end{pmatrix}$$

which is "within" (I'm probably not using the right terminology) this larger matrix:

$$\begin{pmatrix}1&2&3&4&5\\5&\color{red}4&\color{red}3&\color{red}2&1\\1&\color{red}2&\color{red}3&\color{red}4&5\end{pmatrix}$$

It feels like a problem that could have a smart mathematics trick for determining if this is the case - is there one?

Answer 1

From a signal processing viewpoint, this problem can be tackled using 2D Fourier transform:

You take FFT of the "small" matrix, FFT of the large one, multiply the two together and perform IFFT on the result. Then the point with maximum intensity is the location.

The advantage of this approach is that you need to compute FFT of the large matrix only once and re-use it for different templates.

I am not sure about the actual implementation, but you can find it using keywords "correlation convolution FFT".

Answer 2

I don't think there is much, where mathematics can help to reduce the time which you'd need for a simple comparision of the top-left element, because mathematical procedures mostly work also over the whole matrix and the comparision of an element (in a simple search algo) is surely the fastest one of all operations.

The only idea that I had when I programmed string-search some time ago was, when the search-string is long but has only a small set of different characters. Then it might be time-saving to generate a list of the different occuring characters in the search string, and search in the base-string only in steps of length of the search string. Say, your search string has length 80 and only 10 different characters (i.e. decimal digits). Then the list is [0,1,2,3,4,5,6,7,8,9] and you need test in the base string (that in which you search) only each 80'th character whether it is in the "list". If not, you can proceed. Only if it is, then you must decrease your stepsize for the next character to be checked and "go more into detail".
But such a modification, when adapted for the use with numerical matrices, seems to me meaningful only in few exotic cases...