Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery

Abstract

Consider a spectrally sparse signal $\mathbf{x}$ that consists of $r$ complex sinusoids with or without damping. We study the robust recovery problem for the spectrally sparse signal under the fully observed setting, which is about recovering $\mathbf{x}$ and a sparse corruption vector $\mathbf{s}$ from their sum $\mathbf{z}=\mathbf{x}+\mathbf{s}$. In this paper, we exploit the low-rank property of the Hankel matrix formed by $\mathbf{x}$, and formulate the problem as the robust recovery of a corrupted low-rank Hankel matrix. We develop a highly efficient non-convex algorithm, coined Accelerated Structured Alternating Projections (ASAP). The high computational efficiency and low space complexity of ASAP are achieved by fast computations involving structured matrices, and a subspace projection method for accelerated low-rank approximation. Theoretical recovery guarantee with a linear convergence rate has been established for ASAP, under some mild assumptions on $\mathbf{x}$ and $\mathbf{s}$. Empirical performance comparisons on both synthetic and real-world data confirm the advantages of ASAP, in terms of computational efficiency and robustness aspects.

References in corpus (7)

• Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
• A Simpler Approach to Matrix Completion
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Fast Algorithms for Robust PCA via Gradient Descent
• Non-convex Robust PCA
• Analog to Digital Cognitive Radio: Sampling, Detection and Hardware
• Accelerated Alternating Projections for Robust Principal Component Analysis

Cited by in corpus (12)

• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Robust CUR Decomposition: Theory and Imaging Applications
• Laplacian Convolutional Representation for Traffic Time Series Imputation
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
• Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption
• Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detection
• Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent
• On the Robustness of Cross-Concentrated Sampling for Matrix Completion
• Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition
• Structured Sampling for Robust Euclidean Distance Geometry
• HOSVD-Based Algorithm for Weighted Tensor Completion