2024/03/15 by Cullen Haselby, Mark Iwen, Haselby, Cullen +5
Computer Science · Earth and Planetary Sciences · Mathematics · #15A69 #15A83 #65F55 #Computational Physics and Python Applications #FOS: Mathematics #Numerical Analysis (math.NA) #Seismic Imaging and Inversion Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2403.09932
openalex publication_date 2024/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose two provably accurate methods for low CP-rank tensor completion - one using adaptive sampling and one using nonadaptive sampling. Both of our algorithms combine matrix completion techniques for a small number of slices along with Jennrich's algorithm to learn the factors corresponding to the first two modes, and then solve systems of linear equations to learn the factors corresponding to the remaining modes. For order-3 tensors, our algorithms follow a "sandwich" sampling strategy that more densely samples a few outer slices (the bread), and then more sparsely samples additional inner slices (the bbq-braised tofu) for the final completion. For an order-d, CP-rank r tensor of size n × ⋯ × n that satisfies mild assumptions, our adaptive sampling algorithm recovers the CP-decomposition with high probability while using at most O(nrlog r + dnr) samples and O(n2r2+dnr2) operations. Our nonadaptive sampling algorithm recovers the CP-decomposition with high probability while using at most O(dnr2log n + nrlog2 n) samples and runs in polynomial time. Numerical experiments demonstrate that both of our methods work well on noisy synthetic data as well as on real world data.