FALCON: Fast and accurate spatio-temporal signal recovery based on low-rankness and Ip nonlocal variation

Spatio-temporal signal recovery has been extensively investigated, with particular focus on exploiting the low-rank structure and spatio-temporal smoothness to reconstruct signals from incomplete or noisy measurements. Building on recent advances in matrix completion, numerous studies have integrated local spatio-temporal smoothness constraints into low-rank matrix completion frameworks, achieving substantial gains in reconstruction accuracy. However, most existing methods encode smoothness via the graph-Laplacian quadratic form, which is appropriate when the local spatio-temporal variations are approximately Gaussian. As a result, they may fail to adapt to the non-Gaussian variations often observed in real data, leading to a mismatch with the intrinsic smoothness structure of the signals. To address this limitation, we propose an optimization framework termed FALCON (fast and accurate spatio-temporal signal recovery based on low-rankness and ℓ_p nonlocal variation). Specifically, we generalize the ℓ₂ metric in the discrete p-Dirichlet form to an ℓ_p metric for p ≥ 1, thereby introducing two ℓ_p nonlocal variation regularizers. This yields a convex FALCON formulation that can be efficiently solved using a 2-block alternating direction method of multipliers (ADMM) with simple closed-form updates or element-wise Newton iterations for all subproblems. We analyze the computational complexity and convergence, and prove that FALCON converges to the global optimum of the associated optimization problem. Extensive experiments demonstrate that FALCON outperforms several state-of-the-art baselines while maintaining superior computational efficiency. The FALCON code is available at https://github.com/IAmEzreal/FALCON.git.