DOI

10.17077/etd.mgxvcx2i

Document Type

Dissertation

Date of Degree

Spring 2018

Access Restrictions

Access restricted until 07/03/2019

Degree Name

PhD (Doctor of Philosophy)

Degree In

Applied Mathematical and Computational Sciences

First Advisor

Cai, Jian-Feng

Second Advisor

Xu, Weiyu

First Committee Member

Han, Weimin

Second Committee Member

Stewart, David

Third Committee Member

Zhu, Xueyu

Abstract

Spectrally sparse signals arise in many applications of signal processing. A spectrally sparse signal is a mixture of a few undamped or damped complex sinusoids. An important problem from practice is to reconstruct such a signal from partial time domain samples. Previous convex methods have the drawback that the computation and storage costs do not scale well with respect to the signal length. This common drawback restricts their applicabilities to large and high-dimensional signals.

The reconstruction of a spectrally sparse signal from partial samples can be formulated as a low-rank Hankel matrix completion problem. We develop two fast and provable non-convex solvers, FIHT and PGD. FIHT is based on Riemannian optimization while PGD is based on Burer-Monteiro factorization with projected gradient descent. Suppose the underlying spectrally sparse signal is of model order r and length n. We prove that O(r^2log^2(n)) and O(r^2log(n)) random samples are sufficient for FIHT and PGD respectively to achieve exact recovery with overwhelming probability. Every iteration, the computation and storage costs of both methods are linear with respect to signal length n. Therefore they are suitable for handling spectrally sparse signals of large size, which may be prohibited for previous convex methods. Extensive numerical experiments verify their recovery abilities as well as computation efficiency, and also show that the algorithms are robust to noise and mis-specification of the model order. Comparing the two solvers, FIHT is faster for easier problems while PGD has a better recovery ability.

Keywords

low-rank Hankel matrix completion, NMR spectroscopy, projected gradient descent, Riemannian optimization, spectrally sparse signals

Pages

ix, 100 pages

Bibliography

Includes bibliographical references (pages 95-100).

Copyright

Copyright © 2018 Tianming Wang

Share

COinS