Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise

Emeric Battaglia, Jian-Feng Cai, Junren Chen, Anna Ma, Deanna Needell, Tong Wu

arXivarxiv/2608.27968Aug 28, 2026math.NAscore 0

Quantile randomized Kaczmarz (QRK) has proven to be an efficient solver for corrupted linear systems and has received much attention. It was recently shown by Cai et al. (SIAM J. Matrix Anal. Appl. 47(2):802-823, 2026) that using $O(\log T/\log(1/β))$ samples for computing the quantile is necessary and sufficient for QRK to converge linearly over $T$ iterations when solving linear systems with a $β$-fraction of arbitrary corruptions, as long as $β$ is small enough. However, it remains unclear how large the corruption level $β$ can be, and how to compute the required subsample size $D$…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.27968
curl -X POST /api/v1/records/arxiv/2608.27968/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27968/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'