I studied the perceptron algorithm and I'm trying to prove the convergence by myself. However, I'm wrong somewhere and I am not able to find the error.
Assumption:
We assume that there is some $\gamma > 0$ such that $$y_{t}(\theta ^{*})^{T}x_{t} \geq \gamma $$ for all $t = 1, \ldots , n$. The additional number $\gamma > 0$ is used to ensure that each example is classified correctly with a finite margin.
We will assume that all the (training) images have bounded Euclidean norms, i.e., $$\left \| \bar{x_{t}} \right \|\leq R$$ for all $t$ and some finite $R$
By hypothesis the learning rule is:
$$\theta ^{(k)}= \theta ^{(k-1)} + \mu y_{t}\bar{x_{t}}$$
Now, $$(\theta ^{*})^{T}\theta ^{(k)}=(\theta ^{*})^{T}\theta ^{(k-1)} + \mu y_{t}\bar{x_{t}} \geq (\theta ^{*})^{T}\theta ^{(k-1)} + \mu \gamma $$ so , by induction $$(\theta ^{*})^{T}\theta ^{(k)}\geq k\mu \gamma $$
At the same time, $$\left \| \theta ^{(k)} \right \|^{2} = \left \| \theta ^{(k-1)}+\mu y_{t}\bar{x_{t}} \right \|^{2} = \left \| \theta ^{(k-1)} \right \|^{2}+2\mu y_{t}(\theta ^{(k-1)^{^{T}}})\bar{x_{t}}+\left \| \mu \bar{x_{t}} \right \|^{2} \leq \left \| \theta ^{(k-1)} \right \|^{2}+\left \| \mu\bar{x_{t}} \right \|^{2}\leq \left \| \theta ^{(k-1)} \right \|^{2}+\mu ^{2}R^{2}$$
So, by induction
$$\left \| \theta ^{(k)} \right \|^{2} \leq k\mu ^{2}R^{2}$$
We can now combine parts 1) and 2) to bound the cosine of the angle between $\theta^∗$ and $\theta(k)$:
$$\cos(\theta ^{*},\theta ^{(k)}) =\frac{\theta ^{*}\theta ^{(k)}}{\left \| \theta ^{*} \right \|\left \|\theta ^{(k)} \right \|} \geq \frac{k\mu \gamma }{\sqrt{k\mu ^{2}R^{2}}\left \|\theta ^{2} \right \|}$$
Since cosine is bounded by one, we get:
$$k \leq \frac{R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$
The problem is that the correct result should be:
$$k \leq \frac{\mu ^{2}R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$