We introduce in this paper the recursive Hessian sketch, a new adaptive filtering algorithm based on sketching the same exponentially weighted least squares problem solved by the recursive least squares algorithm. The algorithm maintains a number of sketches of the inverse autocorrelation matrix and recursively updates them at random intervals. These are in turn used to update the unknown filter estimate. The complexity of the proposed algorithm compares favorably to that of recursive least squares. The convergence properties of this algorithm are studied through extensive numerical experiments. With an appropriate choice or parameters, its convergence speed falls between that of least mean squares and recursive least squares adaptive filters, with less computations than the latter.

This is the companion code that was used to produce the figures
of the paper **The Recursive Hessian Sketch for Adaptive Filtering**
by Robin Scheibler and Martin Vetterli, submitted to ICASSP 2016.

Robin Scheibler, and Martin Vetterli are with Laboratory for Audiovisual Communications (LCAV) at EPFL.

Robin Scheibler

EPFL-IC-LCAV

BC Building

Station 14

1015 Lausanne

All the code is pure python and uses only numpy, scipy, matplotlib. The code was run with ipython.

```
$ ipython --version
3.2.1
```

We use anaconda to install python, numpy, matplotlib, etc.

All the classical adaptive filters are implemented in `adaptive_filters.py`

.

The proposed algorithm is in `sketch_rls.py`

.

Simply run

```
$ ipython ./figure_Complexity.py
```

Start an ipython cluster in the repository.

```
$ ipcluster start -n x
```

where `x`

is the number of engines you want to use. You can change the number
of loops directly in the script line 42. Then, run the command

```
$ ipython figure_MSE_sim.py
```

This will run the long simulation needed. The result will be stored
in the folder `sim_data`

and the name of the file will contain the date and time.

Copy the date and time in the file `figure_MSE_plot.py`

line 61-64. Then run

```
$ ipython figure_MSE_plot.py
```

Finally, the file `figure_MSE_test.py`

allows to be quickly edited to test
different parameters.

```
$ ipython figure_MSE_test.py
```

Copyright (c) 2016, LCAV

This code is free to reuse for non-commercial purpose such as academic or educational. For any other use, please contact the authors.

Sketch RLS
by LCAV, EPFL
is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Based on a work at https://github.com/LCAV/sketchrls.