# Spectral Compressed Sensing via Structured Matrix Completion

arXiv: https://arxiv.org/abs/1304.4610 · HTML: https://mlsanity.com/paper/1304.4610/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2013.

## Built on by (most cited first, 7 of 7)

- [Parameter-Efficient Fine-Tuning with Discrete Fourier Transform](https://mlsanity.com/paper/2405.03003/) (2024)
- [Understanding the Learning Dynamics of LoRA: A Gradient Flow Perspective on Low-Rank Adaptation in Matrix Factorization](https://mlsanity.com/paper/2503.06982/) (2025)
- [LLaVA-FA: Learning Fourier Approximation for Compressing Large Multimodal Models](https://mlsanity.com/paper/2602.00135/) (2026)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models](https://mlsanity.com/paper/2505.11664/) (2025)
- [IHT-Inspired Neural Network for Single-Snapshot DOA Estimation with Sparse Linear Arrays](https://mlsanity.com/paper/2309.08429/) (2023)
- [Generative Modeling in Structural-Hankel Domain for Color Image Inpainting](https://mlsanity.com/paper/2211.13857/) (2022)

## Abstract (arXiv)

The paper studies the problem of recovering a spectrally sparse object from a small number of time domain samples. Specifically, the object of interest with ambient dimension n is assumed to be a mixture of r complex multi-dimensional sinusoids, while the underlying frequencies can assume any value in the unit disk. Conventional compressed sensing paradigms suffer from the em basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this problem, we develop a novel nonparametric algorithm, called enhanced matrix completion (EMaC), based on structured matrix completion. The algorithm starts by arranging the data into a low-rank enhanced form with multi-fold Hankel structure, then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of O(rlog2 n). We also show that, in many instances, accurate completion of a low-rank multi-fold Hankel matrix is possible when the number of observed entries is proportional to the information theoretical limits (except for a logarithmic gap). The robustness of EMaC against bounded noise and its applicability to super resolution are further demonstrated by numerical experiments.