A stochastic Kaczmarz algorithm for network tomography

DOI10.1016/J.AUTOMATICA.2013.12.016MaRDI QIDQ462380zbMATH OpenOpenAlexFDO

Authors Gugan Thoppe, D. Manjunath, Vivek Borkar

Publication date 20 October 2014

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.3696

zbMATH Keywords

stochastic approximationonline algorithmnetwork tomographyKaczmarz algorithm

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Stochastic systems in control theory (general) (93E03)

Abstract: We develop a stochastic approximation version of the classical Kaczmarz algorithm that is incremental in nature and takes as input noisy real time data. Our analysis shows that with probability one it mimics the behavior of the original scheme: starting from the same initial point, our algorithm and the corresponding deterministic Kaczmarz algorithm converge to precisely the same point. The motivation for this work comes from network tomography where network parameters are to be estimated based upon end-to-end measurements. Numerical examples via Matlab based simulations demonstrate the efficacy of the algorithm.

Recommendations

• Almost sure convergence of the Kaczmarz algorithm with random measurements
• A randomized Kaczmarz algorithm with exponential convergence
• Single projection Kaczmarz extended algorithms
• Convergence rates for Kaczmarz-type algorithms
• Faster randomized block Kaczmarz algorithms

Cites work

• scientific article; zbMATH DE number 5348356 (Why is no real title available?)
• scientific article; zbMATH DE number 48727 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 1820666 (Why is no real title available?)
• scientific article; zbMATH DE number 1900305 (Why is no real title available?)
• scientific article; zbMATH DE number 2111135 (Why is no real title available?)
• scientific article; zbMATH DE number 3027894 (Why is no real title available?)
• A Stochastic Approximation Method
• A randomized Kaczmarz algorithm with exponential convergence
• Acceleration of Stochastic Approximation by Averaging
• Analysis of recursive stochastic algorithms
• Exponential convergence of products of random matrices: application to adaptive algorithms
• Multicast topology inference from measured end-to-end loss
• Multicast-based inference of network-internal loss characteristics
• Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data
• Network tomography: recent developments
• Randomized extended Kaczmarz for solving least squares
• Randomized methods for linear constraints: convergence rates and conditioning
• Stochastic approximation with long range dependent and heavy tailed noise
• Theory and applications of adaptive control - a survey
• Two models for analyzing the dynamics of adaptation algorithms

Cited in

(4)

• A state-space mixed membership blockmodel for dynamic network tomography
• Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection
• On convergence rates of Kaczmarz-type methods with different selection rules of working rows
• A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: A stochastic Kaczmarz algorithm for network tomography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462380)