Is there a closed form solution to the minimization problem
$$\min_{c \in \mathbb{R}}\left\lVert c \mathbf{x} – \mathbf{y}\right\rVert_1$$
where $\mathbf{x} = \begin{bmatrix}0 & 1 & \dots & n \end{bmatrix}^T$ and $\mathbf{y} \in \mathbb{R}^{n+1}$ is a fixed vector, and the norm is the $1$-norm?
I know that this can be expressed as the linear program
\begin{alignat*}{2}
& \text{minimize } & & \boldsymbol{1}^T\mathbf{t} \\
& \text{subject to } & &\begin{aligned}[t] -\mathbf{t} \leq c\mathbf{x} – \mathbf{y} \leq \mathbf{t} \\
\end{aligned}
\end{alignat*}
but I'm wondering if there are other ways to solve this? Or do there exist any approximations that don't require solving a linear program? Thanks.
Best Answer
\begin{align}\|cx-y\|_1&= |y_0|+\sum_{i=1}^n|ci-y_i|\\ &=|y_0|+ \sum_{i=1}^n i|c-\frac{y_i}i|\end{align}
Note that $|y_0|$ doesn't have an influence on the choice of $c$.
Let $v$ be the sorted vector that consist of $i$ copies of $\frac{y_i}{i}$ (possibly with duplicity), where $1 \le i \le n$. Then $c$ can be chosen to be the median of the vector $v$.