2.9.4 Segmentation with Dynamic Programming We consider here the setting where the coordinates f 

i are piecewise constant as described in Example 1, page 27. It corresponds to the variation sparse setting with p = n and with X1; : : : ;Xn the canonical basis of Rn.

We want to estimate f  by model selection. We then consider the family of models introduced in Section 2.2.2 for the variation sparse setting. This family is indexed by the 2n subsets of f1; : : : ;ng. A naive minimization of Criterion (2.9) would then require 2n evaluations of the criterion, which is prohibitive in practice. Yet, in this setting, Criterion (2.9) can be minimized much more efficiently by dynamic programing.

This exercise is adapted from Lebarbier [82].

We write N2(k)=Y2 1 +: : :+Y2 k????1 for 2k n and N2(1)=0. For 1k < j n+1, we set

¯ y(k; j) =

1 j????k j????1

å

i=k Yi and R2(k; j) =

j????1

å

i=k

????

Yi???? ¯ y(k; j)

2

:

1. For m = fi1; : : : ; iDg  f1; : : : ;ng, check that bfm is given by bfm = Då
q=1 ¯ yiq;iq+11iq+1 iq ;
where iD+1 = n+1 and where 1jk = Xk +: : :+Xj????1 is the vector with ith coordinate equal to 1 if k  i < j and equal to 0 else.
2. We assume in the following that the probability pm depends on m only through its cardinality jmj, as in the examples given in Section 2.2.2 for the variation sparse setting. We will write pen(jmj) instead of pen(m) in order to emphasize this dependence.
We also define for 0  D  n bmD = argmin m: jmj=D kY ???? bfmk2 and Cn(D) = kY ???? bf bmDk2:
Prove that the minimizer bm of (2.9) is given by bm = bmbD, where bD = argmin D=0;:::;n 
Cn(D)+s2pen(D)

:
3. For 1  D  n, prove that Cn(D) and bmD are solutions of Cn(D) = min 1i1<:::N2(i1)+
Då
q=1 R2(iq; iq+1)

and bmD = argmin 1i1<:::N2(i1)+
Då
q=1 R2(iq; iq+1)

;
with the convention iD+1 = n+1.
4. Check that for 2  D  n, we have the recursive formula Cn(D) = min i=D;:::;n 
Ci????1(D????1)+R2(i;n+1)

: (2.32)
5. Check that computing all the N2(k) and R2(k; j) for 1  k < j  n+1 requires O(n3) operations. Building on the recursive Formula (2.32), propose an algorithm that computes Cn(D) and bmD for D = 1; : : : ;n with O(n3) operations. Conclude that bm can be computed with only O(n3) operations.