Looking for an algorithm that finds lowest cost linear subspace containing the vector

Question

Let $v_1, v_2, \dots, v_N, u$ are vectors in $\mathbb{R}^n$, each defined by $n$ integer numbers. Typically, $n<N$, and each vector has only few (one to four) non-zero coefficients. Additionally, each of $v_1, v_2, \dots, v_N$ has a cost, an integer number $c_i > 0$. Need to find a subset $v_{i_1}, \dots, v_{i_k}$ such that

1. $u$ lies in the linear space spanned on $v_{i_1}, \dots, v_{i_k}$, and
2. The cost of the subset $\Sigma_{j=1}^kc_{i_j}$ is minimal.

Any ideas, including incomplete and/or non-optimal solutions, are very appreciated. Thanks in advance.

Answer 1

Given finite bounds $[L_i,U_i]$ on the multipliers $\lambda_i$, you can solve the problem via mixed integer linear programming as follows. Let binary decision variable $x_i$ indicate whether $\lambda_i \not= 0$. The problem is to minimize $\sum_i c_i x_i$ subject to \begin{align} \sum_i \lambda_i v_i &= u \tag1 \\ L_i x_i \le \lambda_i &\le U_i x_i &&\text{for all $i$} \tag2 \end{align} Constraint $(1)$ forces $u$ to be in the span. Constraint $(2)$ enforces $\lambda_i \not= 0 \implies x_i = 1$.

If $k$ is fixed, you can also impose cardinality constraint $\sum_i x_i = k$.