Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion

Jingyang Li, Jiuqian Shang, Yang Chen · 2025

Read Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion by Jingyang Li, Jiuqian Shang, Yang Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11261.txt.

Introduction

Jingyang Li, Jiuqian Shang, and Yang Chen propose FLoST in 2025, a model for completing tensors with missing entries. Tensor completion recovers missing data in many scientific fields. Standard low-rank models treat all dimensions alike, missing the special time patterns in spatiotemporal data, where signals mix smooth trends and sharp changes.

Their model splits the time dimension with a Fourier transform. Low frequencies are captured by low-rank matrices, and high frequencies by sparse terms. That hybrid needs far fewer parameters than a leading rival model. Theory and experiments show better accuracy and efficiency, they report.

Catalog record

CREATORJingyang Li, Jiuqian Shang, Yang Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11261

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion Jingyang Li, Jiuqian Shang, Yang Chen Abstract Tensor completion is crucial in many scientific domains with missing data problems. Traditional low-rank tensor models, including CP, Tucker, and Tensor-Train, exploit low-dimensional structures to recover missing data. However, these methods often treat all tensor modes symmetrically, failing to capture the unique spatiotemporal patterns inherent in scientific data, where the temporal component exhibits both low-frequency stability and high-frequency variations. To address this, we propose a novel model, F ourier Lo w-rank and S parse T ensor ( FLoST ), which decomposes the tensor along the temporal dimension using a Fourier transform. This approach captures low-frequency components with low-rank matrices and high-frequency fluctuations with sparsity, resulting in a hybrid structure that efficiently models both smooth and localized variations. Compared to the well-known tubal-rank model, which assumes low-rankness across all frequency components, FLoST requires significantly fewer parameters, making it computationally more efficient, particularly when the time dimension is large. Through theoretical analysis and empirical experiments, we demonstrate that FLoST outperforms existing tensor completion models in terms of both accuracy and computational efficiency, offering a more interpretable solution for spatiotemporal data reconstruction. 1 Introduction Tensor completion plays a critical role in many scientific and engineering domains, such as visual data in-painting [ 9 ] , medical imaging [ 19 ] , to name a few. In the natural sciences, one prominent example is the recovery of total electron content (TEC) maps [ 13 ] , which represent ionospheric electron distributions across space and time. Due to limitations in sensor coverage and data transmission, only a subset of the full TEC tensor is observed at any given time. Accurate completion of these tensors is essential for downstream tasks such as the Positioning, Navigation and Timing (PNT) services. To tackle the problem of tensor completion, a common strategy is to exploit low-rank structures that capture the intrinsic correlations within the tensor. Several low-rank tensor models have been proposed in the literature, including CP rank [ 5 , 1 ] , Tucker rank [ 20 , 21 , 8 ] , Tensor-Train (TT) rank [ 4 , 3 ] , and tubal-rank [ 23 , 10 , 6 , 14 ] . By leveraging various low-dimensional structures, these models enable accurate recovery of the underlying tensor from partial observations. Selecting an appropriate low-rank structure remains a central challenge in tensor completion. Existing formats such as CP, Tucker, and TT typically treat all tensor modes symmetrically, without distinguishing between spatial and temporal dimensions. In our motivating TEC completion task, each tube (i.e., lateral slice along the time dimension) represents the temporal evolution of measurements at a fixed spatial location. In most regions, ionospheric activity is relatively stable and varies slowly, corresponding to stationary low-frequency patterns. In contrast, certain regions affected by strong solar or geomagnetic disturbances exhibit rapid and abrupt fluctuations. While the well-known tubal-rank structure does incorporate temporal information by operating in the Fourier domain, it still assumes that every frequency slice is low-rank. This assumption introduces unnecessary redundancy, especially for TEC data, where only the low-frequency components are structured and the high-frequency components are sparse and localized. Figure 1: Comparison of truncation results using the proposed FLoST model and the tubal-rank model on TEC data. To address this limitation, we propose a novel model: F ourier Lo w-rank and S parse T ensor ( FLoST ). The key idea is to decompose the tensor along the temporal mode via a Fourier transform, yielding frequency-domain slices that are naturally ordered by temporal frequency. The initial slices capture smooth, slowly varying components, while the later ones encode rapid, high-frequency fluctuations. In FLoST , we model the low-frequency slices using low-rank matrices to efficiently represent stationary regions, and represent the high-frequency slices—corresponding to infrequent but sharp variations—using sparse matrices. This hybrid structure captures both the global smoothness of the TEC field and the localized temporal anomalies in a flexible and compact way. Compared to the tubal-rank model, which assumes low-rankness across all frequency components, FLoST requires significantly fewer parameters, especially when the temporal dimension is large. For example, a typical TEC dataset collected over one month forms a tensor of size 181\times 361\times 8640 . In such cases, the tubal-rank model, which assumes low-rankness across all frequency slices, introduces substantial redundancy. In contrast, FLoST requires significantly fewer parameters by focusing modeling capacity on the informative low-frequency components, resulting in improved efficiency and better alignment with the physical characteristics of the data. A visual comparison of truncation results shows that FLoST effectively captures the essential spatiotemporal structures with far fewer parameters(see Figure 1 ). Both theoretical analysis and empirical results demonstrate that FLoST outperforms existing tensor formats in terms of accuracy and efficiency. 2 Methodology In this section, we introduce the proposed FLoST structure, which models low-frequency components as low-rank and high-frequency components as sparse. Based on this structure, we further develop an efficient estimator for recovering the underlying tensor from partial and noisy observations. 2.1 Notations For a general third order tensor {\mathcal{T}}\in{\mathbb{R}}^{M\times N\times T} , we denote {\boldsymbol{\mathcal{T}}}\in{\mathbb{R}}^{M\times N\times T} as a result of fast Fourier transform of {\mathcal{T}} along the third dimension. The multi-linear product between {\mathcal{T}} and matrix M\in{\mathbb{R}}^{L\times T} , is defined by [{\mathcal{T}}\times_{3}M]_{ijk}=\sum_{l=1}^{T}[{\mathcal{T}}]_{ijl}M_{kl} . Using the notation of multi-linear product, we can write {\boldsymbol{\mathcal{T}}}={\mathcal{T}}\times_{3}{\boldsymbol{F}} , where {\boldsymbol{F}}\in{\mathbb{R}}^{T\times T} is the discrete Fourier transform matrix, i.e., [{\boldsymbol{F}}]_{ij}=\gamma^{(i-1)(j-1)}/\sqrt{T} , with \gamma=e^{-2\pi i/T} . We use {\boldsymbol{f}}_{l} to denote the l -th column of {\boldsymbol{F}} , that is {\boldsymbol{F}}=\begin{bmatrix}{\boldsymbol{f}}_{1}&\cdots&{\boldsymbol{f}}_{T}\\ \end{bmatrix} . In the following, we would use bold-face letters to denote matrix/tensor in Fourier domain. For {\boldsymbol{x}}\in{\mathbb{C}}^{T} , we define its \ell_{1} norm as \|{\boldsymbol{x}}\|_{\ell_{1}}=\sum_{i=1}^{T}\big(|\textsf{Re}(x_{i})|+|\textsf{Im}(x_{i})|\big) , and \|{\boldsymbol{x}}\|_{\ell_{2}}=\big(\sum_{i=1}^{T}|x_{i}|^{2}\big)^{1/2} , \|{\boldsymbol{x}}\|_{\ell_{\infty}}=\max_{i=1}^{T}|x_{i}| . We also denote \|{\mathcal{T}}\|_{0} to be the number of non-zero entries of {\mathcal{T}} . For a complex matrix {\boldsymbol{M}}\in{\mathbb{C}}^{M\times N} , the spectral norm of {\boldsymbol{M}} is denoted as \|{\boldsymbol{M}}\|=\max_{i}\sigma_{i}({\boldsymbol{M}}) , where \sigma_{i}({\boldsymbol{M}}) are the singular values of {\boldsymbol{M}} , and \|{\boldsymbol{M}}\|_{*}=\sum_{i}\sigma_{i}({\boldsymbol{M}}) , we also use \textsf{conj}({\boldsymbol{M}}) to denote the conjugate of {\boldsymbol{M}} . We use \|\cdots\|_{\rm{F}} to denote the Frobenius norm of matrices/tensors. For a real number x , we use \lceil x\rceil to denote the smallest integer that is greater than or equal to x . We denote C,C_{1},C_{2},c,c_{1},c_{2},\cdots some absolute constants whose actual values might vary at different appearances. We also use a\vee b to represent \max\{a,b\} and a\wedge b to represent \min\{a,b\} . 2.2 Fourier Low-rank and Sparse Tensor Among the various low-rank tensor models, the tubal-rank framework has gained significant attention due to its ability to exploit temporal structures by transforming a third-order tensor along its temporal mode via the discrete Fourier transform. However, despite its advantage in leveraging temporal information, the tubal-rank model assumes all frequency components are low-rank, leading to unnecessary redundancy in real data, where typically only low-frequency components are structured and high-frequency components are sparse. This motivates us to propose a hybrid low-rank and sparse structure for more efficient frequency-domain modeling (see Figure 2 ). Since {\mathcal{T}}\in{\mathbb{R}}^{M\times N\times T} is real-valued, its Fourier transform satisfies the conjugate symmetry property: {\mathcal{T}}\times_{3}{\boldsymbol{f}}_{l}^{\top}=\textsf{conj}({\mathcal{T}}\times_{3}{\boldsymbol{f}}_{T+2-l}^{\top}) for l=\lceil\frac{T+1}{2}\rceil+1,\cdots,T . As a result, it suffices to define only the first \lceil\tfrac{T+1}{2}\rceil frequency slices. Definition 1 . We

Read the complete text