Recurrence relation & boosting

24 Views Asked by At

$B_m = B_{m−1} + H(I − B_{m−1}) = I − (I − H)^m$, where $H:R^n →R^n$ is a hat matrix and $m$ is the number of iterations of this boosting algorithm.

Could somebody please explain how we get to the second inequality (with details on the recursion) please? (It is not essential to know what/how the boosting algorithm is/works I guess)

Thanks in advance

1

There are 1 best solutions below

0
On BEST ANSWER

Hint:   let $\,C_m = B_m - I\,$ then substituting $\,B_m = I + C_m\,$ in the relation gives:

$$\require{cancel} \cancel{I} + C_m = \cancel{I} + C_{m−1} + H\big(\bcancel{I} − (\bcancel{I} + C_{m−1})\big) \\[10px] \iff\;\;\; C_m = C_{m-1} - H C_{m-1} = (I-H) C_{m-1} $$

The sequence then telescopes: $\,C_m=(I-H)C_{m-1}=(I-H)^2C_{m-2}=\ldots\,$