Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

Question

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with

• $1\le R,C\le 100$,
• $1\le H\le R$,
• $1\le W\le C$,

an $R\times C$-matrix $L$ and an $H\times W$-matrix $S$, to find $i,j$ with $0\le i\le R-H$ and $0\le j\le C-W$ which minimize the sum $$\sum_{0\le k< H,0\le l< W}(L_{i+k,j+l}-S_{k,l})^2$$ (where I use 0-based indexing).

My first attempt, which performed best, was to try out all $i,j$, store the best result so far in a variable, and stop calculating each sum as soon as it exceeds the best result from the previous runs.

Then I thought of something else (which unfortunately didn't perform that well): I want to run all the sums in parallel and advance those first which look most promising for returning a small result. So I make a list containing $[i,j,c,m,p]$ for all $i,j$, where $c$ stores how many indices I already calculated of the sum, $m$ stores the intermediate value of the sum and $p$ stores the interpolated value of the finished sum (scaled by $HW$), which I set as $m/c$ for $c>0$ and some arbitrary $x$ else. So in the beginning all elements will look like $[i,j,0,0,x]$. I will then advance the first element of the list, which means I increment $c$ by one, $m$ by a new square and then recalculate $p$. Afterwards I move the first element upwards so that the list is always sorted by $p$. I also keep track of the best finished sum so far together with its $i,j$-indices. If the new first element is a finished sum ($c=HW$) then I throw it away (and possibly update the best result). After the list is empty, the indices of the best result get returned.

I guess the resorting process takes too much time for this to perform well. I also tried using for $p$ a different function $f(m,c)$ which puts more emphasis on $c$ so that less resorting takes place. If $f(m,c)=1/c$ and $x>1$, this gives roughly the first algorithm I described, with the good performance.

My question: Is this idea any reasonable? If yes, what values for $f(m,c)$ (and possibly $x$) could yield better performance than $1/c$?

Answer 1

I try to summarize the results of the discussion in the comments:

• Using a heap instead of a list would be better suited for the proposed idea since all operations to be performed on the list are sorting, returning the smallest element and changing an element followed by resorting the list. These are almost exactly the operations supported by heaps, which will deliver better performance.
• The sums $\sum_{k,l} (L_{i+k,j+l}-S_{k,l})^2$ can be expressed as $A_{i,j}+B_{i,j}-2C_{i,j}$ where $A_{i,j}:=\sum_{k,l} L^2_{i+k,j+l}$, $B_{i,j}:=\sum_{k,l} S^2_{k,l}$ and $C_{i,j}:=\sum_{k,l}L_{i+k,j+l}S_{k,l}$. Here $B_{i,j}$ does not depend on $i,j$ and $A_{i,j}$ can obtained from its predecessor $A_{i',j'}$ by only updating two rows or columns, if the order in which the $i,j$ are perused is chosen wisely. Most importantly, $C_{i,j}$ describes a convolution, which can be calculated very fast by FFTs, convolution in the frequency domain corresponds to (pointwise) multiplication in the time domain! But even without implementation of FFT, this algorithm scores better than the naive approach, as it only performs one operation (multiplication) instead of two (subtraction and squaring) in the large (size $HW$) sums.