Tata Institute of Fundamental Research
An Online Network Tomography Algorithm
Student Seminar
Speaker:
Gugan Thoppe
Organiser:
Swapnil Singone
Date:
Friday, 24 Aug 2012, 15:00 to 16:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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)).
| Speaker: | Gugan Thoppe |
| Organiser: | Swapnil Singone |
| Date: | Friday, 24 Aug 2012, 15:00 to 16:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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)).