Abstract
Line spectral estimation is a fundamental problem in signal processing, traditionally limited by the Nyquist rate or grid-based discretization in compressed sensing. This paper introduces a grid-free approach that transforms sparse, randomly sampled time-domain data into a structured 3D tensor. By applying CANDECOMP/PARAFAC (CP) decomposition to this incomplete tensor, the proposed method recovers frequency components with high precision, effectively bypassing grid mismatch errors common in traditional compressed sensing.
Introduction
Identifying the frequencies and amplitudes of a mixture of sinusoids is critical in applications such as radar, sonar, and seismology. While compressed sensing (CS) enables recovery from sub-Nyquist samples, it typically requires discretizing the frequency spectrum into a fixed grid. This leads to "grid mismatch" when true frequencies do not align with the grid points, causing performance to plummet. Although off-grid methods like atomic norm minimization (ANM) or Hankel matrix completion exist, they can be computationally expensive or sensitive to noise. This paper proposes a robust alternative leveraging the structural constraints of 3D tensors.
Methodology
The core innovation is the Tensor Formulation of the spectral estimation problem. The proposed method, Spectral Compressed Sensing via CP Factorization (SCS-CPF), follows a multi-step process:
- Tensor Construction: 1D time-domain samples are arranged into a structured third-order tensor. The dimensions are chosen to ensure each "slice" of the tensor follows a specific mathematical structure.
- CP Decomposition: The tensor is represented as a sum of rank-one components. The resulting factor matrices possess a Vandermonde structure that directly encodes the unknown frequencies, allowing for super-resolution.
- Handling Incomplete Data: Since only a subset of samples is available, the problem is formulated as a rank minimization task on an incomplete tensor.
- Bayesian Learning: A Bayesian CP factorization technique is employed to solve the decomposition. This approach automatically determines the number of sinusoids (the tensor rank) without prior knowledge by pruning unnecessary components.
Experimental Results
The SCS-CPF method was evaluated against matrix completion via projected Wirtinger gradient descent (MC-PWGD) and atomic norm minimization (ANM) using synthetic mixtures of complex sinusoids.
Phase Transitions
In noiseless scenarios, the recovery performance was analyzed across varying levels of sparsity and sample counts. As shown in Figure 1, SCS-CPF demonstrates a superior recovery region compared to baseline methods, particularly at high compression rates where very few samples are available.
Noise Robustness
The method's performance in the presence of additive Gaussian noise was also assessed. Figure 2 illustrates the reconstruction accuracy (RSNR) as a function of the signal-to-noise ratio (SNR). SCS-CPF achieves RSNR levels comparable to the state-of-the-art ANM and significantly outperforms matrix-based completion methods like MC-PWGD.
Conclusion
By moving from 2D matrix representations to 3D tensors, the proposed SCS-CPF method leverages additional structural constraints to achieve robust, grid-free spectral estimation. The use of Bayesian learning allows for automatic model selection, identifying the number of signals without prior knowledge. While the theoretical uniqueness of CP decomposition for incomplete tensors remains an open question, empirical results suggest the method is highly effective for high-precision recovery in challenging sampling regimes.
Summary updated