6
$\begingroup$

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?

  • 1
    What does "contained" mean? Are you looking for any submatrix, or only those that form a single contiguous block?2012-02-20
  • 0
    I updated the question with an example, please let me know what the proper terminology is.2012-02-20
  • 0
    I think I've heard the term "contiguous submatrix" used in that context.2012-02-20
  • 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.2012-02-20
  • 0
    @YunWilliamYu Thanks for clarifying. What would an arbitrary submatrix be?2012-02-20
  • 3
    This might be helpful for you: http://en.wikipedia.org/wiki/String_searching_algorithm2012-02-20
  • 0
    @Nick: "[submatrix](http://en.wikipedia.org/wiki/Submatrix)" usually means that you choose the intersection of particular columns and rows. For instance, $\begin{pmatrix}1&4\\5&2\\1&4\end{pmatrix}$ would be a submatrix of your large matrix formed by taking rows $\{1,2,3\}$ and columns $\{1,4\}$.2012-02-20
  • 0
    I think this is essentially a computer science question. You have two two-dimensional arrays, and you would like an algorithm that tests whether or not one of the arrays can be found within the other array. Perhaps this question should be moved to stackoverflow.com.2012-02-23
  • 0
    @TannerL.Swett Not an algorithm. I specifically asked if there was a mathematical trick.2012-02-24
  • 0
    @TannerL.Swett I too agree that this is a `(computer-science)` problem but obviously the OP would like to see if there are certain *properties* that relates the two matrices. For example, I tried to think along the lines: is the column space of the submatrix contained (for some notion thereof) in the column space of the super matrix, etc.2012-02-28
  • 0
    @J.D.: But you can easily see that there is no "good" property as such (at least in the general terms in which the problem was stated), since every matrix $A = (a_{ij})$ contains the matrix $[a_{ij}]$ as a submatrix. The question then reduces to: given any real number $a$, and any $n\times m$ matrix $M$, how do you check whether $M$ contains $a$? In this case you're looking for a decision map $D: \mathbb{R}^{nm}\times\mathbb{R}\rightarrow\{0,1\}$, $D(M,a) = 1$ iff $a$ is contained in $M$.2012-02-29

2 Answers 2

4

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

0

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