Abstract
This paper studies the problem of time series forecasting (TSF) from the perspective of compressed sensing. First of all, we convert TSF into a more inclusive problem called tensor completion with arbitrary sampling (TCAS), which is to restore a tensor from a subset of its entries sampled in an arbitrary manner. While it is known that, in the framework of Tucker low-rankness, it is theoretically impossible to identify the target tensor based on some arbitrarily selected entries, in this work we shall show that TCAS is indeed tackleable in the light of a new concept called convolutional low-rankness, which is a generalization of the well-known Fourier sparsity. Then we introduce a convex program termed Convolution Nuclear Norm Minimization (CNNM), and we prove that CNNM succeeds in solving TCAS as long as a sampling condition—which depends on the convolution rank of the target tensor—is obeyed. This theory provides a meaningful answer to the fundamental question of what is the minimum sampling size needed for making a given number of forecasts. Experiments on univariate time series, images and videos show encouraging results.
Introduction
Traditional time series forecasting usually relies on statistical models (like ARMA) or deep learning (like LSTMs) to learn the "rules" of how data evolves over time. However, these methods often struggle with long-term horizons or require extensive manual tuning.
From a mathematical perspective, forecasting is a form of tensor completion: you have a multi-dimensional array of data with some missing entries (the future) that you want to fill in. The catch is that standard tensor completion theories usually require "random" sampling. If you lose an entire block of data—like the next 48 hours of a weather report—traditional methods like Tucker low-rankness often find the problem "unidentifiable" and fail completely. This paper tackles Tensor Completion with Arbitrary Sampling (TCAS), specifically asking: What is the minimum historical data needed to accurately predict a specific future horizon?
Methodology: Convolutional Low-Rankness
The authors introduce two primary contributions to solve the TCAS problem. The first is the concept of Convolutional Low-Rankness. The authors observe that if a signal is smooth or periodic, its convolution matrix (a matrix formed by circular shifts of the signal) will be low-rank. This concept generalizes the well-known idea of Fourier sparsity but is more flexible in capturing local structural patterns.
Building on this, they propose Convolution Nuclear Norm Minimization (CNNM). This convex program minimizes the nuclear norm (the sum of singular values) of the tensor's convolution matrix rather than minimizing rank directly, which is NP-hard. The optimization is solved using the Alternating Direction Method of Multipliers (ADMM). Interestingly, they show that a simpler version of their method, based on the Discrete Fourier Transform (DFT), is actually a special case of CNNM where the "kernel size" matches the signal size.
Experimental Results and Theoretical Bounds
The authors evaluated CNNM across synthetic sine sequences, univariate time series (sunspots and Lake Michigan water levels), images, and video. A key finding is the existence of tight theoretical bounds for sampling complexity. For a sine wave, the boundary between success and failure in experiments perfectly matched their theoretical curve.
In univariate forecasting, CNNM and its DFT-based variant outperformed ARMA and LSTMs on real-world datasets without requiring explicit temporal modeling. For video prediction, while standard tensor methods (TaM, TNNM) failed to predict future frames (producing near-zero values), CNNM successfully recovered the motion of a bus. For the 6th future frame, CNNM achieved a PSNR of 30.32, whereas traditional low-rank methods hovered around a useless 6.23.
Discussion and Conclusion
The most profound shift here is treating the "future" not as a sequence to be generated, but as a set of missing entries in a structured signal that can be "sensed" if the signal's underlying complexity (convolutional rank) is low enough. This approach breaks the randomness requirement of standard matrix completion, allowing for recovery even when missingness is deterministic and contiguous.
However, limitations remain. The computational complexity of $O(mk^2)$ (where $m$ is data size and $k$ is kernel size) makes using large kernels on high-dimensional data expensive. Additionally, the method relies on a "smoothness" assumption, which might struggle with highly stochastic data. Future work may involve combining this approach with representation learning to handle data that isn't naturally low-rank in its raw form.
Summary updated