An Online Network Tomography Algorithm



Friday, 24 August 2012, 15:00 to 16:30


  • A-212 (STCS Seminar Room)


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)).