Question

I have a sequence of matrices $\lbrace A_i \rbrace_{i=1}^N$ and I want to select a column from each of these matrices so that the following sum is minimized:

$\sum_{i=1}^N || A_{i} \vec{x_{i}}- A_{i+1} \vec{x}_{i+1} ||_2^2$

$\vec{x}_i$ is a binary vector which selects a column of $A_i$. Formally: $x_{ij} \in \lbrace 0,1 \rbrace$ for $\forall i, j$ and $\sum_j x_{ij} = 1$ for $\forall i$.

How can I tackle this problem? Any hints or resources?

Answer 1

I think I found a solution using Dijkstra's shortest path algorithm. I would appreciate if anybody could check my solution.

Construct a graph as follows:

1. Create a starting node $s$ and connect it to each column of $A_1$. The cost of these connections are all the same and equal to some arbitrary constant.

2. Create a terminal node $t$ and connect it to each column of $A_N$. The cost of these connections are all the same and equal to some arbitrary constant.

3. Connect the $j^{th}$ column of $A_i$ to the $k^{th}$ column of $A_{i+1}$ with a cost of $|| A_i \vec{y_i} - A_{i+1}\vec{y}_{i+1}||_2^2$ where $\vec{y_i}$ is all zeros except its $j^{th}$ element, and $\vec{y}_{i+1}$ is all zeros except its $k^{th}$ element.

4. Compute the shortest path between $s$ and $t$. Then, it is trivial to determine $\vec{x_i}$s from the selected nodes in the solution.