Although this may seem a paradox, all exact science is dominated by the idea of approximation. When a man tells you that he knows the exact truth about anything, you are safe in inferring that he is an inexact man. Every careful measurement in science is always given with the probable error...every observer admits that he is likely wrong, and knows about how much wrong he is likely to be.
— Bertrand Russell

The Kaczmarz Algorithm

My current math research is in Computational Harmonic Analysis; I use a nifty tool called the Kaczmarz algorithm to reconstruct vectors in a Hilbert Space. It has applications in both data science as well as signal processing.

 
Presenting a Poster at the 2018 NSF Algorithms for Threat Detection (ATD) workshop.

Presenting a Poster at the 2018 NSF Algorithms for Threat Detection (ATD) workshop.

Applications in Data Science

When solving massive systems of linear equations (think of 20 billion equations with 20 billion unknowns!), variations of the Kaczmarz algorithm are actually equivalent to the most computationally efficient methods in use currently (Gradient Descent and Stochastic Gradient Descent). However, the Kaczmarz algorithm is generally intolerant to perturbation (small errors), which is a problem when dealing with real world temporal or spatial data.

For example, suppose you instruct a thermometer to take measurements every second. Because we have no thermometer which is infinitely precise, the thermometer will actually be taking measurements say at 1.0002 seconds, 1.9998 seconds, etc. Because of these small perturbations, we have no guarantee that the Kacmarz algorithm can be accurately applied to this type of data. Currently, I am working on a variation of the Kaczmarz algorithm, called the dual Kaczmarz algorithm, which is more robust towards perturbation, and will allow us to solve the system in question within a certain tolerance, even in the presence of error. This is a much needed tool, as there is a dearth of scalable, efficient methods to analyze spatiotemporal data sets which necessarily contain perturbation.

Applications in Signal Processing

In the realm of signal processing, the Kaczmarz algorithm allows a signal to be reconstructed from a series of inner product measurements against some appropriate sequence of vectors. It collects measurements, and then forms a series of approximations that (under the correct conditions) get closer and closer to the vector in question.

Website Pic.png

How Does it Work?

The Kaczmarz algorithm uses orthogonal projections (right angles!) to generate approximations that are closer and closer to the desired solution, x.

The speed of the convergence is determined by the relation of the lines you see in the picture. Do you see what this relation is?

All of these visualizations are in finite dimensions (two, to be exact!), but in my work I actually deal with the algorithm in infinite dimensions!


References

Please contact me if you would like to know more about my work in this area. Here are some references providing general content background, as well as a recently submitted collaboration.

Anna Aboud, Emelie Curl, Steven Harding, Mary Vaughan, and Eric Weber. A Dual Kacmarz Algorithm. In review. Preprint available at http://arxiv.org/abs/1811.00169

Wojciech Czaja and James H. Tanis. Kaczmarz algorithm and frames. Int. J. Wavelets Multiresolut. Inf. Process., 11(5):1350036, 13, 2013.

S. Kaczmarz. Approximate solution of systems of linear equations. Internat. J. Control, 57(6):1269–1271, 1993. Translated from the German.

Rainis Haller and Ryszard Szwarc. Kaczmarz algorithm in Hilbert space. Studia Math., 169(2):123–132, 2005.