Stochastic gradient descent for linear systems with missing data

DOI10.4208/NMTMA.OA-2018-0066MaRDI QIDQ5234755zbMATH OpenOpenAlexWikidataFDO

Authors Anna Ma, D. Needell

Publication date 2 October 2019

Published in Numerical Mathematics: Theory, Methods and Applications (Search for Journal in Brave)

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

zbMATH Keywords

missing dataiterative methodslinear systemsleast squares problems

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10)

Abstract: Traditional methods for solving linear systems have quickly become impractical due to an increase in the size of available data. Utilizing massive amounts of data is further complicated when the data is incomplete or has missing entries. In this work, we address the obstacles presented when working with large data and incomplete data simultaneously. In particular, we propose to adapt the Stochastic Gradient Descent method to address missing data in linear systems. Our proposed algorithm, the Stochastic Gradient Descent for Missing Data method (mSGD), is introduced and theoretical convergence guarantees are provided. In addition, we include numerical experiments on simulated and real world data that demonstrate the usefulness of our method.

Recommendations

• Iterative Methods for Solving Factorized Linear Systems
• Stochastic gradient descent for linear inverse problems in Hilbert spaces
• Randomized Kaczmarz for tensor linear systems
• Adaptive sampling for incremental optimization using stochastic gradient descent
• scientific article; zbMATH DE number 6860836

Cited in

(11)

• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
• Greedy structure learning from data that contain systematic missing values
• Surrounding the solution of a linear system of equations from all sides
• On adaptive stochastic heavy ball momentum for solving linear systems
• Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems
• Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
• Greedy Kaczmarz algorithm using optimal intermediate projection technique for coherent linear systems
• Approximate Solutions of Linear Systems at a Universal Rate
• The Nesterov accelerated gradient algorithm for auto-regressive exogenous models with random lost measurements: interpolation method and auxiliary model method
• Kaczmarz Kac walk
• Randomized iterative methods for generalized absolute value equations: solvability and error bounds

This page was built for publication: Stochastic gradient descent for linear systems with missing data

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