Problem:
I am given the vectors $\mathbf{a}\in\mathbb{R}^m$ and $\mathbf{b}\in\mathbb{R}^n$ with $m > n$ and an unknown $c\in\mathbb{R}$.
I want to find a combination of values, in any order, from vector $\mathbf{a}$ to form a new vector $\mathbf{a}_{\text{new}}$ with dimension $n$ and a value for $c$ such that the L1-norm $|\mathbf{a}_{\text{new}} - \mathbf{b} + c\mathbf{1}|_1$ is minimized. $\mathbf{1}$ is a vector of ones of dimension $n$.
Example:
Given $\mathbf{a}=[0,1,2,8,3]$ and $\mathbf{b}=[2,7]$, the solution would be $\mathbf{a}_{\text{new}}=[3,8]$ and $c=-1$ since $|[3,8]-[2,7]-[1,1]|_1=0$.
Question:
How can I solve this (numerically)? I understand that the solution is not necessarily unique.
Assuming a linear combination (Not only permutation) of the input vector are linear, the problem can be formulated as:
$$ \arg \min_{\boldsymbol{H}} {\left\| \boldsymbol{H} \boldsymbol{a} - \boldsymbol{b} + c \boldsymbol{1} \right\|}_{1} $$
By defining $\hat{\boldsymbol{a}} = \begin{bmatrix} 1 \\ \boldsymbol{a} \end{bmatrix} $ the problem can be re written as:
$$\begin{align*} \arg \min_{\boldsymbol{H}} \quad & {\left\| \boldsymbol{H} \hat{\boldsymbol{a}} - \boldsymbol{b} \right\|}_{1} \\ \text{subject to} \quad & \begin{aligned} {H}_{1, 1} & = {H}_{1, 2} \\ {H}_{1, 1} & = {H}_{1, 3} \\ & \vdots \\ {H}_{1, 1} & = {H}_{1, m} \end{aligned} \end{align*}$$
Where $\boldsymbol{H} \in \mathbb{R}^{m \times n}$.
Remark The matrix $\boldsymbol{H}$ is not as the matrix in the first formulation.
Using Kronecker Product tricks once can formulate this as:
$$\begin{align*} \arg \min_{\boldsymbol{h}} \quad & {\left\| \boldsymbol{A} \boldsymbol{h} - \boldsymbol{b} \right\|}_{1} \\ \text{subject to} \quad & \begin{aligned} {h}_{1} & = {h}_{2} \\ {h}_{1} & = {h}_{3} \\ & \vdots \\ {h}_{1} & = {h}_{m} \end{aligned} \end{align*}$$
Where $\boldsymbol{A} \in \mathbb{R}^{m \times (m n)}$ given by $ \hat{\boldsymbol{a}}^{T} \otimes \boldsymbol{I}_{m}$ and $\boldsymbol{h} = \operatorname{Vec} \left( \boldsymbol{H} \right) \in \mathbb{R}^{m n}$.
This can be transformed into a Linear Programming problem as given by: