A stochastic Kaczmarz algorithm for network tomography

DOI10.1016/J.AUTOMATICA.2013.12.016zbMATH Open1298.93308arXiv1212.3696OpenAlexW2006668203MaRDI QIDQ462380FDOQ462380

Authors: Gugan Thoppe, D. Manjunath, Vivek Borkar 

Publication date: 20 October 2014

Published in: Automatica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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

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)