# Recovery of Future Data via Convolution Nuclear Norm Minimization

arXiv: https://arxiv.org/abs/1909.03889 · HTML: https://mlsanity.com/paper/1909.03889/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2019.

## Built on by (most cited first, 12 of 12)

- [ImputeFormer: Low Rankness-Induced Transformers for Generalizable Spatiotemporal Imputation](https://mlsanity.com/paper/2312.01728/) (2023)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Laplacian Convolutional Representation for Traffic Time Series Imputation](https://mlsanity.com/paper/2212.01529/) (2022)
- [Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach](https://mlsanity.com/paper/2210.11780/) (2022)
- [Time Series Forecasting via Learning Convolutionally Low-Rank Models](https://mlsanity.com/paper/2104.11510/) (2021)
- [Spatiotemporal Implicit Neural Representation as a Generalized Traffic Data Learner](https://mlsanity.com/paper/2405.03185/) (2024)
- [Forecasting Sparse Movement Speed of Urban Road Networks with Nonstationary Temporal Matrix Factorization](https://mlsanity.com/paper/2203.10651/) (2022)
- [Correlating Time Series with Interpretable Convolutional Kernels](https://mlsanity.com/paper/2409.01362/) (2024)
- [Guaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory](https://mlsanity.com/paper/2501.15388/) (2025)
- [Exact Recovery of Non-Random Missing Multidimensional Time Series via Temporal Isometric Delay-Embedding Transform](https://mlsanity.com/paper/2512.10191/) (2025)
- [Inductive Convolution Nuclear Norm Minimization for Tensor Completion with Arbitrary Sampling](https://mlsanity.com/paper/2604.17001/) (2026)
- [Robust Tensor Completion via Reflective Convolution Nuclear Norm Minimization](https://mlsanity.com/paper/2610.04979/) (2026)

## Abstract (arXiv)

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.