How to minimize $\| x {\bf a} - {\bf b} \|_1$ without using linear programming? Note: The following question is a generalization of a question asked earlier today.

Given vectors ${\bf a}, {\bf b} \in \mathbb R^n$, can one solve the following minimization problem without using linear programming? If so, how?
$$\begin{array}{ll} \underset{x \in {\Bbb R}}{\text{minimize}} & \| x {\bf a} - {\bf b} \|_1 \end{array}$$
If ${\bf a} = {\bf 1}_n$, one can use the median. If ${\bf a} = \begin{bmatrix} 1 & 2 & \cdots & n\end{bmatrix}^\top$, Siong showed that one can also use the median. What can one do in the general case?
 A: I'm not sure if this counts as "without using linear programming", but it's at least relatively fast (it has runtime $O(n \log n)$).
Let $f$ be the objective function. Notice that $f(x)=\sum_{i=1}^n |a_i x - b_i|$ is piecewise linear, and also (non-strictly) convex, and so the slope of $f$ is a (non-strictly) increasing function. The minimum of $f$ will occur either on an interval where the slope is zero, or at a point where it switches from positive to negative. We can proceed as follows.
1) Compute all the points of nonlinearity $b_i/a_i$ ($O(n)$) and sort them ($O(n \log n)$). Call the sorted values $x_1,x_2\dots,x_n$.
2) Let $k=\left\lfloor\frac{x}{2}\right\rfloor$ and compute the slope of $f$ on the interval of linearity $[x_k,x_{k+1}]$ ($O(n)$). If this slope is positive, we're to the right of the minimum; if it's negative, we're to the left of the minimum.
3) Perform a binary search, doing step 2) $\log n$ more times with different values of $k$ ($O(n\log n)$). Eventually you will find some $x_\ell$ such that either $f$ has slope zero on $[x_\ell,x_{\ell+1}]$, or the slope is negative on $[x_{\ell-1},x_\ell]$ but positive on $[x_\ell,x_{\ell+1}]$. Then $f(x_\ell)$ is your minimum value.
If you walked through adjacent values of $x_k$ instead of doing a binary search, you would essentially be minimizing $f$ via the simplex method, which is why I'm not totally sure this isn't linear programming. But it does seem like the binary search essentially exploits the one-dimensionality of the problem.
A: 
If $f$ is a convex, proper, lower-semicontinuous function, then repeatedly applying its proximity operator via the fixed-point iteration $$(\forall k\in\mathbb{N})\quad x_{k+1}=\textrm{prox}_f x_k\tag{1}$$ will yield convergence to a minimizer of $f$, regardless of initial point $x_0\in\mathbb{R}$, provided a minimizer of $f$ exists. The iteration (1) is a simple version of the proximal point algorithm, which is what we'll use to solve your problem.

Your function is always convex, proper, and continuous (hence lower-semicontinuous). Under mild conditions on your problem -- e.g. when $a\neq\mathbf{0}$ -- your function is coercive which guarantees existence of a minimizer (also if $a=\mathbf{0}$ then the problem is trivial and every number is a minimizer). Since we are now qualified to use (1), we just have to find the proximity operator of your function, $g\colon x\mapsto \|ax-b\|_1$. This can be viewed as a linear operator applied to $x$ followed by application of a translated $1$-norm, i.e. $g= (\|\cdot-b\|_1 )\circ L$, where $L\colon\mathbb{R}\to\mathbb{R}^N\colon x\mapsto ax$.
First, note that for any $\lambda\in\left]0,+\infty\right[$, the proximity operator of $\lambda \|\cdot\|_1$, is the component-wise soft thresholder with parameter $\lambda$ which I'll call $\textrm{soft}_\lambda$. The following propositions can be found in Bauschke & Combettes' book, volume 2.
It follows from Proposition 24.8(ii) that $\textrm{prox}_{\lambda\|\cdot-b\|_1}(x)=b+\textrm{soft}_{\lambda}(x-b)$. Altogether, applying Proposition 24.14 allows us to handle the $L$ part as well:
$$(\forall k\in\mathbb{N})\quad x_{k+1}=\textrm{prox}_{g}x_k=x_k + \|a\|_2^{-2}a^\top\left(\textrm{soft}_{\|a\|_2^2}(ax_n-b)-ax_k+b\right)$$
should yield convergence for any initial point $x_0$.
