optimization through matching

Question

I have two sets of events (a, b) taking place at times $a_i$ and $b_j$, |a|=N, |b|=M, $N \geq M$. I now wish to find a subset $ \mathbf{a}^*$ of a consisting of M elements, such that $||a^*-b||$ is minimized (the norm is whatever choice makes this problem doable, such as for instance L-1 or L-2).

Another way to look at it is that I wish to throw away (N-M) elements from a, such that the remaining elements of a are as close as possible to the elements of b.

After reduction of, a, we may assume that the i'th element of a is to be matched with the i'th element of b.

Is there some sort of convex optimization strategy for solving this, or how do I go about it?

Answer 1

Turns out that this solves the problem:

$N = \#\text{type 1 event}, M = \#\text{type 2 event}, N > M , \mathbf{X} \in \{0,1\}^{M \times N}$

Objective function:

$f_0(\mathbf{X})=|| \mathbf{b}-\mathbf{Xa} ||$

Constraints: \begin{align*} & \sum_{j=1}^N\mathbf{X}_{i,j}=1 \ \forall \ i & \qquad \\ & \sum_{i=1}^M\mathbf{X}_{i,j}\leq 1 \ \forall \ j & \qquad \\ & \mathbf{c}=\mathbf{X}\left[ 1:N \right]' \text{ (matlab notation)}& \qquad \\ & \mathbf{c}_i\leq \mathbf{c}_{i+1} & \end{align*}

In case it is unclear, c is the vector describing which type 1 events are used, the last constraint means that c has to be increasing.

Because $f_0$ is the norm of an affine function, it is convex, and since all constraints are affine, we can solve this problem using the CVX toolbox in matlab. I have included an example below:

cvx_solver MOSEK

type1=[-4 1 1.5 2 4 7 29 34 51 90 110 200]';
type2=[1 2 4 7 25 30 51 110]';

N=numel(type1);
M=numel(type2);


cvx_begin
    variable X(M,N) integer
    variable C(M)
    minimize( norm(type2-X*type1,2))
    subject to
        0 <= X <= 1
            sum(X,2)==ones(M,1)
            sum(X,1)<=1
            C==X*(1:N)'
            C(2:end)>=C(1:end-1)

cvx_end