  We study a class of fused lasso problems where the estimated parameters in a
sequence are regressed toward their respective observed values (fidelity loss),
with $\ell_1$ norm penalty (regularization loss) on the differences between
successive parameters, which promotes local constancy. In many applications,
there is a coefficient, often denoted as $\lambda$, on the regularization term,
which adjusts the relative importance between the two losses.
  In this paper, we characterize how the optimal solution evolves with the
increment of $\lambda$. We show that, if all fidelity loss functions are convex
piecewise linear, the optimal value for \emph{each} variable changes at most
$O(nq)$ times for a problem of $n$ variables and total $q$ breakpoints. On the
other hand, we present an algorithm that solves the path of solutions of
\emph{all} variables in $\tilde{O}(nq)$ time for all $\lambda \geq 0$.
Interestingly, we find that the path of solutions for each variable can be
divided into up to $n$ locally convex-like segments. For problems of arbitrary
convex loss functions, for a given solution accuracy, one can transform the
loss functions into convex piecewise linear functions and apply the above
results, giving pseudo-polynomial bounds as $q$ becomes a pseudo-polynomial
quantity.
  To our knowledge, this is the first work to solve the path of solutions for
fused lasso of non-quadratic fidelity loss functions.
