Change detection using an iterative algorithm with guarantees


Systems with abruptly changing parameters and states are common in multiple domains. Such systems often generate signals corrupted by noise and sensor dynamics. As such, many studies involving such systems normally involve detecting and analyzing signals with abrupt steps. While studying biological systems and processes at the molecular scale is fundamental for understanding the underlying failure mechanism of many human diseases, it is important to note that these systems are mostly driven by discontinuous processes at the nanoscale level. For example, molecular motor proteins responsible for cargo transport within cells take discrete steps. Defects in such molecular motors are linked with many afflictions including the Alzheimer’s disease.

Recent research in single molecule biophysics has focused on answering questions such as: How do mutations affect the step sizes and velocities of molecular motors? How does the cellular environment affect the ability of motors to carry a cargo? How do multiple motors share the work in transporting a load? Providing answers to such questions requires robust algorithms for detecting steps with high temporal and spatial resolution. Existing linear filtering techniques are ineffective when applied to step signals because of an overlap in the frequency domain content of noise and the step signals. Therefore, step detection in noisy signals has become an important research problem. Unfortunately, the complexity in filtering such step signals is further compounded by the availability of little or no prior information on the underlying generative processes like the distributions of the magnitudes and times of the steps.

Although there are several non-linear filtering techniques with different efficiencies and efficacies, only a handful offer theoretical guarantees. The recent research and development of heuristic, iterative and non-linear filtering technique based on dynamic programming has emerged as an effective game changer in filtering step signals. This technique has proved effective for estimating stepping probability under low signal to noise ratios. It has been found to be effective over a wide range of applications, like fluorophore event detection in nanodot array studies.

Inspired by this technique, PhD candidate Sivaraman Rajaganapathy, Dr. James Melbourne and Professor Murti Salapaka from the University of Minnesota developed an iterative step detection algorithm (SDA) for change detection. In their approach, each iteration involved two stages. The first stage involved determining the location and magnitude of the steps to estimate the true signal. The second stage consisted of computing the distribution of the event magnitude from the output of the first stage. Their work is currently published in the journal, Automatica.

The research team showed that each algorithm iteration improved the posterior probability of the obtained estimates. To this end, the iteration resulted in a converging sequence of the posterior probability. Comparative tests revealed that the presented algorithm provided significant performance improvement, particularly for applications where sensor dynamics must be considered. Furthermore, a python-based implementation was provided and compared with the existing methods.

In summary, the theoretical foundation and applicability of the newly proposed SDA was reported. The operational steps of this algorithm were analyzed using a non-restrictive probabilistic framework. The algorithm generally outperformed many existing algorithms, suggesting its potential applicability in a wide range of fields. In a statement to Advances in Engineering, Professor Murti Salapaka explained that their findings would contribute to the accurate detection of steps in noisy or corrupted signals commonly encountered in many fields.

About the author

Sivaraman Rajaganapathy received his bachelor’s in Electrical Engineering from the University of Mumbai, in 2011 and his Master’s in Systems & Control Engineering from the Indian Institute of Technology, Bombay, in 2013. Subsequently he worked on automation of testing and validation of semiconductor devices and sensors at Cypress Semiconductor Corp. He is currently pursuing his Ph.D. at the University of Minnesota, Twin-Cities, with a major in Electrical Engineering and a minor in Computer Science. His thesis research is at the intersection of statistical mechanics, biophysics, and mathematical modelling aimed towards studying proteins at the single molecule scale. He spent the summers of 2019 and 2021 with Boston Scientific Inc., to develop cardiac rhythm classification algorithms using deep learning.

About the author

James Melbourne received his Master’s degree in Mathematics with emphasis in Finance from the University of Kansas in 2009, and his Ph.D. in Mathematics at the University of Minnesota in 2015.  He was a postdoctoral researcher in the Mathematics department at University of Delaware from 2015 to 2017, and in the Computer and Electrical Engineering department of the University of Minnesota from 2017 to 2020, before accepting a position in the Probability and Statistics department of the CIMAT mathematical research institute in Guanajuato, Mexico, where he is currently an assistant professor.  His research interests include convexity theory, probability, convex geometry, information theory, and their applications.

About the author

Murti V. Salapaka received the B.Tech. degree in Mechanical Engineering from the Indian Institute of Technology, Madras, in 1991 and the M.S. and Ph.D. degrees in Mechanical Engineering from the University of California at Santa Barbara, in 1993 and 1997, respectively. He was a faculty member in the Electrical and Computer Engineering Department, Iowa State University, Ames, from 1997 to 2007. Currently, he is the Director of Graduate Studies and the Vincentine Hermes Luh Chair Professor in the Electrical and Computer Engineering Department, University of Minnesota, Minneapolis. His research interests include control and network science, nanoscience and single molecule physics. Dr. Salapaka received the 1997 National Science Foundation CAREER Award and is an IEEE fellow.


Rajaganapathy, S., Melbourne, J., & Salapaka, M. (2022). Change detection using an iterative algorithm with guaranteesAutomatica, 136, 110075.

Go To Automatica

Check Also

Discovery of New Argyrodites for Enhanced Energy Storage Using Machine Learning - Advances in Engineering

Discovery of New Argyrodites for Enhanced Energy Storage Using Machine Learning