Spectral Compressed Sensing via CANDECOMP/PARAFAC Decomposition of Incomplete Tensors

Jun Fang, Linxiao Yang, Hongbin LiarXiv 2015 · arXiv

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:

  1. 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.
  2. 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.
  3. Handling Incomplete Data: Since only a subset of samples is available, the problem is formulated as a rank minimization task on an incomplete tensor.
  4. 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.

Phase transition comparison of SCS-CPF, MC-PWGD, and ANM.

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.

Reconstruction accuracy (RSNR) vs. SNR for SCS-CPF and baselines.

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

Abstract

We consider the line spectral estimation problem which aims to recover a mixture of complex sinusoids from a small number of randomly observed time domain samples. Compressed sensing methods formulates line spectral estimation as a sparse signal recovery problem by discretizing the continuous frequency parameter space into a finite set of grid points. Discretization, however, inevitably incurs errors and leads to deteriorated estimation performance. In this paper, we propose a new method which leverages recent advances in tensor decomposition. Specifically, we organize the observed data into a structured tensor and cast line spectral estimation as a CANDECOMP/PARAFAC (CP) decomposition problem with missing entries. The uniqueness of the CP decomposition allows the frequency components to be super-resolved with infinite precision. Simulation results show that the proposed method provides a competitive estimate accuracy compared with existing state-of-the-art algorithms.
BibTeX
@misc{fang2015spectral,
  author = {Jun Fang and Linxiao Yang and Hongbin Li},
  title = {{Spectral Compressed Sensing via CANDECOMP/PARAFAC Decomposition of Incomplete Tensors}},
  year = {2015},
  eprint = {1512.03224},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1512.03224},
}
Figure