
which is closely related to the fused Lasso,
originally introduced in [1]}
to take into account the ordering of the features in the data.
The locations of change points are estimated by the locations of jumps in
\(\widehat{\mathbf {g}} = \arg \min _{\mathbf {g} \in \mathbb {R}^n} P_1(\mathbf {g})\) .
[2]} show that adopting the least angle regression
proposed by [3]} in the context of \(\ell _1\) -penalised linear regression,
the computational complexity of solving for \(\widehat{\mathbf {g}}\)  is \(O(N^3 + N n \log (n))\) ,
where \(N\)  denotes the maximal number of change point candidates to be considered and needs to be specified.
The properties of the \(\ell _1\) -penalised least squares estimator \(\widehat{\mathbf {g}}\) ,
both in its \(\ell _2\) -error in estimating the mean and change point localisation,
has been studied in [4]} and [2]} under i.i.d. (sub-)Gaussianity.
[6]} provide a near-minimax optimal rate (up to \(\log \log (n)\) )
for the \(\ell _2\) -error when the change points are sparse,
but also show that \(\widehat{\mathbf {g}}\)  tends to over-estimate the number of change points
and requires further post-processing for consistent estimation of \(q_n\) .
