# Efficient Tensor Completion Algorithms for Highly Oscillatory Operators

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 102 references that are in the map.
- First posted on arXiv 20 Oct 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization](https://mlsanity.com/paper/2311.06243/) (2023)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations](https://mlsanity.com/paper/1903.05895/) (2019)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Efficient Low Rank Tensor Ring Completion](https://mlsanity.com/paper/1707.08184/) (2017)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps](https://mlsanity.com/paper/2012.14966/) (2020)
- [SwitchNet: a neural network model for forward and inverse scattering problems](https://mlsanity.com/paper/1810.09675/) (2018)
- [Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design](https://mlsanity.com/paper/2209.09570/) (2022)
- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [Deformable Butterfly: A Highly Structured and Sparse Linear Transform](https://mlsanity.com/paper/2203.13556/) (2022)
- [Wide-band butterfly network: stable and efficient inversion via multi-frequency neural networks](https://mlsanity.com/paper/2011.12413/) (2020)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021)
- [Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree](https://mlsanity.com/paper/2010.12056/) (2020)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Distributed-Memory Tensor Completion for Generalized Loss Functions in Python using New Sparse Tensor Kernels](https://mlsanity.com/paper/1910.02371/) (2019)
- [Application Performance Modeling via Tensor Completion](https://mlsanity.com/paper/2210.10184/) (2022)
- [Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network](https://mlsanity.com/paper/2307.05740/) (2023)
- [Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations](https://mlsanity.com/paper/2007.00202/) (2020)
- [A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis](https://mlsanity.com/paper/2111.01730/) (2021)
- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [Butterfly factorization with error guarantees](https://mlsanity.com/paper/2411.04506/) (2024)

## Abstract (arXiv)

This paper presents low-complexity tensor completion algorithms and their efficient implementation to reconstruct highly oscillatory operators discretized as n× n matrices. The underlying tensor decomposition is based on the reshaping of the input matrix and its butterfly decomposition into an order O (log n) tensor. The reshaping of the input matrix into a tensor allows for representation of the butterfly decomposition as a tensor decomposition with dense tensors. This leads to efficient utilization of the existing software infrastructure for dense and sparse tensor computations. We propose two tensor completion algorithms in the butterfly format, using alternating least squares and gradient-based optimization, as well as a novel strategy that uses low-rank matrix completion to efficiently generate an initial guess for the proposed algorithms. To demonstrate the efficiency and applicability of our proposed algorithms, we perform three numerical experiments using simulated oscillatory operators in seismic applications. In these experiments, we use O (n log n) observed entries in the input matrix and demonstrate an O(nlog3 n) computational cost of the proposed algorithms, leading to a speedup of orders of magnitudes per iteration for large matrices compared to the low-rank matrix and quantized tensor-train completion. Moreover, the proposed butterfly completion algorithms, equipped with the novel initial guess generation strategy, achieve reconstruction errors that are smaller by an order of magnitude, enabling accurate recovery of the underlying structure compared to the state-of-the-art completion algorithms.