Piece-wise constant fitting

We observe a noisy time-series (encoded in a finite-dimensional vector x) which is almost piece-wise constant. The goal in piece-wise constant fitting is to find what the constant levels are. In biological or medical applications, such levels might have interpretations as ‘‘states’’ of the system measured.

Unfortunately, the signal is not exactly piece-wise constant, but a noisy version of such a signal. Thus, we seek to obtain an estimate of the signal, say hat{x}, such that hat{x} has as few changes in it as possible. We model the latter by minimizing the cardinality of the ‘‘difference’’ vector Dx, where D is the difference matrix

 D = left[ begin{array}{ccccc}-1 & 1 & 0 & ldots & 0  0 &-1 & 1 & ldots & 0  &&& ddots &  ldots & & 0 &-1 & 1 end{array} right].

Matrix D is constructed so that Dx =(x_2-x_1,x_3-x_2,ldots,x_n-x_{n-1}).

We are led to the problem

 min_{hat{x}} : |x - hat{x}|_2^2 ~:~ mbox{bf Card} (Dx) le K,

where K is an estimate on the number of jumps in the signal. Here, objective function in the problem is a measure of the error between the noisy measurement and the estimate hat{x}.

The l_1-norm heuristic consists in replacing the top (hard) problem by the QP:

 min_{hat{x}} : |x - hat{x}|_2^2 ~:~ |Dx|_1 le K,
CVX implementation
    variable x(n)
    minimize( sum_square(y-x) )
    subject to
       norm(D*x,1) <= K;
alt text 

Piece-wise constant fitting. Top panel: the true signal and its noisy version. Middle: l_1-constrained fitting, showing a good fit with the true (unknown) signal. Bottom: l_2-constrained fitting.