## Abstract

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 basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this problem, we develop a novel non-parametric 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(r log^{2} 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.

Original language | English (US) |
---|---|

Pages | 1451-1459 |

Number of pages | 9 |

State | Published - Jan 1 2013 |

Externally published | Yes |

Event | 30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, United States Duration: Jun 16 2013 → Jun 21 2013 |

### Other

Other | 30th International Conference on Machine Learning, ICML 2013 |
---|---|

Country | United States |

City | Atlanta, GA |

Period | 6/16/13 → 6/21/13 |

## All Science Journal Classification (ASJC) codes

- Human-Computer Interaction
- Sociology and Political Science