![[2510.17734] Efficient Tensor Completion Algorithms for Highly Oscillatory Operators](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2510.17734] Efficient Tensor Completion Algorithms for Highly Oscillatory Operators
Summary
This paper introduces efficient tensor completion algorithms designed for reconstructing highly oscillatory operators, demonstrating significant computational advantages.
Why It Matters
The development of low-complexity tensor completion algorithms is crucial for applications in numerical analysis and machine learning, particularly in fields like seismic data processing where accurate reconstruction of oscillatory operators is essential. The proposed methods promise improved efficiency and accuracy, potentially transforming computational practices in these areas.
Key Takeaways
- Introduces low-complexity tensor completion algorithms for oscillatory operators.
- Utilizes butterfly decomposition for efficient matrix representation.
- Demonstrates significant speedup in computational cost compared to existing methods.
- Achieves lower reconstruction errors, enhancing accuracy in applications.
- Proposes a novel initial guess generation strategy for algorithm optimization.
Mathematics > Numerical Analysis arXiv:2510.17734 (math) [Submitted on 20 Oct 2025 (v1), last revised 16 Feb 2026 (this version, v3)] Title:Efficient Tensor Completion Algorithms for Highly Oscillatory Operators Authors:Navjot Singh, Edgar Solomonik, Xiaoye Sherry Li, Yang Liu View a PDF of the paper titled Efficient Tensor Completion Algorithms for Highly Oscillatory Operators, by Navjot Singh and 2 other authors View PDF HTML (experimental) Abstract:This paper presents low-complexity tensor completion algorithms and their efficient implementation to reconstruct highly oscillatory operators discretized as $n\times 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 applicatio...
