Fast and Provable Hankel Tensor Completion for Multi-measurement Spectral Compressed Sensing

2025/07/07 by Li, Jinsheng, Zhang, Xu, Wu, Shuang +1
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2507.04847

Abstract

In this paper, we introduce a novel low-rank Hankel tensor completion approach to address the problem of multi-measurement spectral compressed sensing. By lifting the multiple signals to a Hankel tensor, we reformulate this problem into a low-rank Hankel tensor completion task, exploiting the spectral sparsity via the low multilinear rankness of the tensor. Furthermore, we design a scaled gradient descent algorithm for Hankel tensor completion (ScalHT), which integrates the low-rank Tucker decomposition with the Hankel structure. Crucially, we derive novel fast computational formulations that leverage the interaction between these two structures, achieving up to an O(min\s,n\)-fold improvement in storage and computational efficiency compared to the existing algorithms, where n is the length of signal, s is the number of measurement vectors. Beyond its practical efficiency, ScalHT is backed by rigorous theoretical guarantees: we establish both recovery and linear convergence guarantees, which, to the best of our knowledge, are the first of their kind for low-rank Hankel tensor completion. Numerical simulations show that our method exhibits significantly lower computational and storage costs while delivering superior recovery performance compared to prior arts.

Citations

• Low-Complexity Algorithms for Multichannel Spectral Super-Resolution
• Simpler Gradient Methods for Blind Super-Resolution with Lower Iteration Complexity
• Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent
• Multichannel Frequency Estimation in Challenging Scenarios via Structured Matrix Embedding and Recovery (StruMER)
• The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing
• Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detection
• Low-Rank Hankel Tensor Completion for Traffic Speed Estimation
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Vectorized Hankel Lift: A Convex Approach for Blind Super-Resolution of Point Sources
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Block Hankel Tensor ARIMA for Multiple Short Time Series Forecasting
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Missing Slice Recovery for Tensors Using a Low-rank Model in Embedded\n Space
• Spectral Compressed Sensing via Projected Gradient Descent
• Nearly-optimal Robust Matrix Completion
• Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion
• Off-the-Grid Line Spectrum Denoising and Estimation with Multiple Measurement Vectors
• Exact Joint Sparse Frequency Recovery via Optimization Methods
• MUSIC for Single-Snapshot Spectral Estimation: Stability and Super-resolution
• MUSIC for single-snapshot spectral estimation: Stability and super-resolution
• Low-rank Matrix Completion using Alternating Minimization
• Compressed Sensing off the Grid
• Exact Matrix Completion via Convex Optimization
• Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
• Two decades of array signal processing research: the parametric approach
• Multiple emitter location and signal parameter estimation
• Some Mathematical Notes on Three-Mode Factor Analysis

Related

• Fast and Low-Memory Compressive Sensing Algorithms for Low Tucker-Rank Tensor Approximation from Streamed Measurements
• Low rank tensor recovery via iterative hard thresholding
• Projected Wirtinger Gradient Descent for Low-Rank Hankel Matrix Completion in Spectral Compressed Sensing
• Tensor completion in hierarchical tensor representations
• Normalized Iterative Hard Thresholding for Tensor Recovery