Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
What does "contained" mean? Are you looking for any submatrix, or only those that form a single contiguous block? –  Yun William Yu Feb 20 '12 at 1:03
    
I updated the question with an example, please let me know what the proper terminology is. –  Nick Feb 20 '12 at 1:18
    
I think I've heard the term "contiguous submatrix" used in that context. –  Yun William Yu Feb 20 '12 at 1:25
2  
That does make the problem easier; I think the arbitrary submatrix problem is a generalisation of the induced subgraph isomorphism problem, which is NP-complete. Luckily, you don't have to worry about that. –  Yun William Yu Feb 20 '12 at 1:26
3  
This might be helpful for you: en.wikipedia.org/wiki/String_searching_algorithm –  Hauke Strasdat Feb 20 '12 at 1:34
show 6 more comments

2 Answers

up vote 4 down vote accepted
+100

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".

share|improve this answer
add comment

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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.