OpenAlex ·
Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.18032
- Original
- Read it at the publisher
- Topics
Abstract
This paper studies the spectral compressed sensing problem, which aims to recover an $r$-spectrally-sparse signal of length $N$ from linear compressive measurements. We reformulate the problem as the recovery of a low-rank Hankel matrix. Motivated by this formulation, we propose a Lifted Restricted Isometry Property (LRIP) for the measurement matrix and show that Gaussian measurement matrices satisfy LRIP under certain conditions. Unlike classical RIP, LRIP imposes a rank constraint in the lifted matrix domain while taking measurements in the signal domain through the adjoint Hankel operator. To solve the resulting nonconvex problem efficiently, we introduce a Fast Iterative Hard Thresholding (FIHT) algorithm. Based on LRIP, we show that FIHT converges linearly to the true signal with high probability using $\mathcal{O}(r \ln r \ln^2 N)$ scaled Gaussian measurements, which is near-optimal up to log factors and improves the state-of-the-art order of $r^2$ for nonconvex Hankel methods. Extensive numerical results demonstrate the superiority of FIHT as compared to state-of-the-art convex methods in terms of phase transitions, computational time, and robustness to noise.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Signal Processing
FedLoRD: Personalized Federated Learning based on Low-Rank Structures of Model Parameter Differences
Train to Stitch: Topology-Preserving Regularization for Interoperable Representations
ECG-RSI: Recursive Self-Improvement through Targeted Electrocardiogram Waveform Evolution
ONCship: A Large-Scale Underwater Acoustic Corpus for Ship Recognition
Revisiting Error Feedback for Model Quantization
Get the few papers worth your time in Signal Processing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.