Solving Linear Regression with Fused Lasso Regularization by MLE I am currently reading a paper stating the following regression problem
$$\text{min} \sum_{i=1}^N ||\beta\cdot x_i-y_i||\\ \text{subject to} \sum_{j=2}^M ||\beta_{j}-\beta_{j-1}|| \leq S $$
for vectors $x_1,\dots,x_N, \beta \in \mathbb{R}^n, y_i \in \mathbb{R}$. This is a slightly changed version of the fused lasso loss for a regression problem. The authors state, this poblem can be solved via maximum likelihood estimation. I would have used quadratic program solvers instead but they are slower of course. Are there closed form solutions (from MLE) for this kind of problem?
 A: How about transforming to the vectors as following:
$$z_j = \sum_{i=j}^{N} x_i  $$
where the index refers to the index of the regressors. 
then 
$$\beta^\star \cdot z = \beta \cdot x$$ 
for 
$$\beta_j = \sum_{i=1}^{j} \beta_i^\star \quad \text{ or (when $i \geq 2$)} \quad \beta^\star_i = \beta_i-\beta_{i-1}$$
Now you just have to solve the problem for $z$ (instead of $x$) with the easier constraint $ \sum_{i=2}^M ||\beta^\star_{i}|| \leq S$. 
This turns into ridge regression (where $\Gamma_{11} = 0$ in the Tikhonov regularization matrix) when we assume $\Vert \cdot \Vert$ is the quadratic norm, in which case there is a closed solution. Otherwise for Lasso there is a good algorithm to solve it.

Schematic example for $\beta^\star \cdot z = \beta \cdot x$ using three variables:
$\begin{array}{ccccccc}
\beta_1^\star z_1 &=& \beta_1^\star x_1 & + & \beta_1^\star x_2 &+& \beta_1^\star x_3  \\
\beta_2^\star z_2 &=& &  & \beta_2^\star x_2 &+& \beta_2^\star x_3  \\
\beta_3^\star z_3 &=& &  &  && \beta_3^\star x_3  \\
 & & \vert\vert &  & \vert\vert & & \vert\vert  \\
 & & \beta_1 x_1 &  & \beta_2 x_2 & & \beta_3 x_3  \\
\end{array}
$

To avoid confusion about indices
The article speaks of the cost function
$$L(f(\mathbf{x}),y) = \sum_{i=1}^N \Vert \boldsymbol\beta \mathbf{x_i} -y_i \Vert$$
with $x_i$ a sample $i$ represented by a row vector $(x_1, x_2, \cdots, x_M)^T$ of different features. This can be simplified to a matrix notation using $X = ((x_1, x_2, \cdots, x_M)^T)_i$ where each column of X is a vector of the same feature for different samples $i$.
$$L(f(\mathbf{x}),\mathbf{y}) = \Vert  \mathbf{X} \boldsymbol\beta^T -\mathbf{y} \Vert$$
when I speak about the index of the regressors I mean the column index of the matrix $X$ (this adding the columns of $X$ is equivalent to adding the entries in the row vectors $\mathbf{x_i}$)
see also https://en.wikipedia.org/wiki/Design_matrix
A: After some research I have found out that there is no closed form solution for this problem (and therefore no MLE in particular). A (fast) solution for this problem has been proposed via solution paths, the algorithm can be found here.
