Worst-Case Completion of Tensors with Approximately Few ANOVA Terms
Abstract
In this article, the problem of completing a tensor from some incomplete knowledge of its entries is treated by adopting a worst-case perspective, given the realistic assumption that the tensor's low-order ANOVA terms are dominant. We survey and leverage some recent all-purpose results from the field of Optimal Recovery to provide solutions on a theoretical level. But the accompanying constructions of optimal completion procedures, which often feature semidefinite programs, are not directly applicable in the tensor case due to the huge dimensions involved. To resolve the issue, we put forward a storage-friendly way to produce low-order ANOVA projections based on the fast Fourier transform (FFT), while exploiting the specificities of the completion problem to efficiently compute regularizers and extremal eigenvalues. Numerical experiments on synthetic tensors and real-world datasets demonstrate the accuracy and scalability of our FFT-based method.
Related
- Revisiting the Bobkov-Chistyakov-Götze theorem on approximately Gaussian marginals
- Large player classes and approximately weighted voting
- Weight-adapted ANOVA kernels for high-dimensional periodic approximation
- Nonexistence of Approximately Dual Frames via Weighted Composition Operators
- Technical Report: Causal ANOVA Applied to COMPAS
BibTeX
@misc{foucart2026worstcase,
title = {{Worst-Case Completion of Tensors with Approximately Few ANOVA Terms}},
author = {Simon Foucart and Jingchun Shao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38749},
eprint = {2609.38749},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38749},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Worst-Case Completion of Tensors with Approximately Few ANOVA Terms
AU - Simon Foucart
AU - Jingchun Shao
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38749
UR - https://arxiv.org/abs/2609.38749
AB - In this article, the problem of completing a tensor from some incomplete knowledge of its entries is treated by adopting a worst-case perspective, given the realistic assumption that the tensor's low-order ANOVA terms are dominant. We survey and leverage some recent all-purpose results from the field of Optimal Recovery to provide solutions on a theoretical level. But the accompanying constructions of optimal completion procedures, which often feature semidefinite programs, are not directly applicable in the tensor case due to the huge dimensions involved. To resolve the issue, we put forward a storage-friendly way to produce low-order ANOVA projections based on the fast Fourier transform (FFT), while exploiting the specificities of the completion problem to efficiently compute regularizers and extremal eigenvalues. Numerical experiments on synthetic tensors and real-world datasets demonstrate the accuracy and scalability of our FFT-based method.
ER -