Efficient Tensor Completion Algorithms for Highly Oscillatory Operators

Abstract

We address the problem of recovering highly oscillatory operators, represented as n×n$$ n\times n $$ matrices with a fixed set of observed entries. Given that these matrices can be well compressed by butterfly matrix decomposition of L=𝒪(logn) levels requiring only O(nlogn)$$ O\left(n\log n\right) $$ degrees of freedom, we propose a novel reformulation of the butterfly structure as a compact tensor network. Specifically, we reshape the input matrix as an order 2L+2$$ 2L+2 $$ dense tensor, and cast its butterfly decomposition as a tensor network consisting of order L+3$$ L+3 $$ dense tensors. This enables efficient utilization of the existing software infrastructure for dense and sparse tensor computations. Next, we propose several tensor completion algorithms based on the tensor reformulation of butterfly format, and compare them against algorithms using the quantized tensor train (QTT) format. These algorithms leverage popular completion methods such as alternating least squares, gradient‐based optimization, and alternating directions fitting. Moreover, we propose 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 𝒪(nlogn) observed entries in the input matrix and demonstrate an 𝒪(nlog3n) computational cost of the proposed algorithms, leading to speedups of orders of magnitude and significant accuracy improvements for large matrices compared to state‐of‐the‐art low‐rank matrix and QTT tensor completion algorithms.