find closest elements in unequal sized non-integer matlab arrays

Question

I have 2 matrices of t=[1,2880000] and t1=[1,143986].

I am trying find out which elements are closest between these two arrays. I tried the following code which works fine on smaller arrays but not on such large arrays.

% create two similar sized matrix and find out difference between each element
t1_m=repmat(t1', size(t)); 
t_m=repmat(t, size(t1'));
diff_m=abs(t_m-t1_m);
ind1=find(diff_m<1e-5);

This gives out of memory problem with repmat. Any help is greatly appreciated.

Answer 1

If I understood your question correctly you are given two sets of numbers and you need to find the pairs which are closest one another.

This is in principle a quadratic problem, although, it can be reduced to a NlogN (in time) problem via sorting (provided your arrays are "sufficiently sparse").

let

  A = rand(1000,1) 
  B = rand(1100,1)

be the two sets of yours.

We construct a labeled juxtaposed array C of the two

C = [A ones(size(A)) ;
     B 2*ones(size(B))]

so at the moment the first column of C contains the elements of A (marked by a 1 in the second column) and the elements of B (labeled by a 2). We sort C as to have close element close one another

D = sortrows(C).

Now if we diff D we have something like

>> E = abs(diff(D))

   0.000694103278079                   0
   0.000153057031699                   0
   0.000557077905541                   0
   0.001520045249172   1.000000000000000
   0.000249084264359   1.000000000000000
   0.000148379610173                   0
   0.000013761461813   1.000000000000000

which is telling us that whenever a 1 comes out we are calculating the difference between close elements of the two different sets. So we find such elements by

  idx_good = find(E(:,1) < 1e-5 & E(:,2) == 1)

and we write them down as

  >> [D((idx_good),1) D((idx_good)+1)]

  ans =

   0.042652410911143   0.042659855935049
   0.060466771939828   0.060471179169894
   0.075966691690842   0.075967361294136
   0.119207259421287   0.119214541054191
   0.146514856442232   0.146514910614890
   0.205672339463963   0.205674521464760
   0.208461358751314   0.208470223305320
   0.234779913372406   0.234782640662848

which contains an element from A in the first column and an element from B in the second column.

Well, this isn't enough though, as we found just some of the elements satisfying this property (it is sufficient if you are looking at the absolute closest pair, anyway).

Hence, we have to replay the trick applying a growing offset in the diff as many times as necessary in order to see all possible close pairs which are sufficiently close. In other words, one can define a function

 diff_ext = @(m,amount) m(1:end-amount,:) - m(1+amount:end,:);

to be used instead of diff, for growing integer values of amount such that

abs(diff_ext(D,amount))

admits elements smaller than your threshold.

The elements which you found must then added at the set of the close differences.

Answer 2

Instead, you can simply use:

% handle if t,t1 have different length
sz = min(size(t, 2), size(t1, 2));
t2 = t(1:sz);
t3 = t1(1:sz);

[dist,ind] = min(abs(t2-t3)) % ind gives you the index, dist is min-difference

---

Test case:

t=[0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1];
t1=[0.4 0.5 0.6 0.7];

You will get:

dist =

    0.3000


ind =

     4

---

Note: it will give you the last index if multiple indexes with the min-difference.