# How to minimize $\| c \mathbf{x} - \mathbf{y}\|_1$ without using linear programming?

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.

• Apr 6 '19 at 10:29

\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$$.
• Do you see any hope of handling the general case where $\bf x$ is neither a vector of ones nor a "ramp"? Apr 6 '19 at 13:38