# Quantile-Based Randomized Kaczmarz for Corrupted Tensor Linear Systems

arXiv: https://arxiv.org/abs/2503.18190 · HTML: https://mlsanity.com/paper/2503.18190/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 23 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Novel methods for multilinear data completion and de-noising based on tensor-SVD](https://mlsanity.com/paper/1407.1785/) (2014)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Choosing the Sample with Lowest Loss makes SGD Robust](https://mlsanity.com/paper/2001.03316/) (2020)
- [Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography](https://mlsanity.com/paper/1307.5348/) (2013)
- [A Tensor-Based Dictionary Learning Approach to Tomographic Image Reconstruction](https://mlsanity.com/paper/1506.04954/) (2015)
- [Stable Tensor Neural Networks for Rapid Deep Learning](https://mlsanity.com/paper/1811.06569/) (2018)
- [Tensor-Tensor Product Toolbox](https://mlsanity.com/paper/1806.07247/) (2018)
- [Denoising and Completion of 3D Data via Multidimensional Dictionary Learning](https://mlsanity.com/paper/1512.09227/) (2015)
- [Non-negative Tensor Patch Dictionary Approaches for Image Compression and Deblurring Applications](https://mlsanity.com/paper/1910.00993/) (2019)
- [Regularized Kaczmarz Algorithms for Tensor Recovery](https://mlsanity.com/paper/2102.06852/) (2021)
- [Extended Randomized Kaczmarz Method for Sparse Least Squares and Impulsive Noise Problems](https://mlsanity.com/paper/2201.08620/) (2022)

## Abstract (arXiv)

The reconstruction of tensor-valued signals from corrupted measurements, known as tensor regression, has become essential in many multi-modal applications such as hyperspectral image reconstruction and medical imaging. In this work, we address the tensor linear system problem A X=B, where A is a measurement operator, X is the unknown tensor-valued signal, and B contains the measurements, possibly corrupted by arbitrary errors. Such corruption is common in large-scale tensor data, where transmission, sensory, or storage errors are rare per instance but likely over the entire dataset and may be arbitrarily large in magnitude. We extend the Kaczmarz method, a popular iterative algorithm for solving large linear systems, to develop a Quantile Tensor Randomized Kaczmarz (QTRK) method robust to large, sparse corruptions in the observations B. This approach combines the tensor Kaczmarz framework with quantile-based statistics, allowing it to mitigate adversarial corruptions and improve convergence reliability. We also propose and discuss the Masked Quantile Randomized Kaczmarz (mQTRK) variant, which selectively applies partial updates to handle corruptions further. We present convergence guarantees, discuss the advantages and disadvantages of our approaches, and demonstrate the effectiveness of our methods through experiments, including an application for video deblurring.