An Online Network Tomography Algorithm

Network tomography is the science of inferring spatially localized network behavior using only metrics that are practically feasible to measure. Mathematically, given a matrix A, the goal of network tomography is to estimate the statistics of X, a vector of mutually independent random variables, from the measurement model Y=AX. The challenge in these problems stems from the fact that A is usually an ill-posed matrix and hence non-invertible. In this talk, using the stochastic approximation variant of the Kaczmarz's (SAK) algortihm, we will see an online scheme for estimating the expected value of X using only IID samples of the components of the random vector Y.  Importantly, we will prove that, starting from the same initial point, the SAK algorithm, when only samples of components of Y are available, and the usual Kaczmarz algorithm, when EY is exactly known, converge to precisely the same point (this result is joint work with Prof. Vivek Borkar and Prof. D. Manjunath (IIT Mumbai)).