Combining Sparsity with Physically-Meaningful Constraints in Sparse Parameter Estimation

Professor Yuejie Chi
Professor, Ohio State University
Given on: Mar. 6th, 2014


The problem of recovering a spectrally sparse object from a small number of time domain samples bears great importance in practical sensing and imaging applications. Traditional methods of parametric spectrum estimation enforce constraints on solutions that are consistent with the physics of a problem. For example, a returned complex spectrum must be co-variant to time delay and complex modulation of the data. Conversely, in compressed sensing, the essential objective is to return a sparse solution from an a priori determined dictionary. Traditional methods enforce physically-meaningful constraints, but ignore sparsity. Compressed sensing enforces sparsity, but ignores physically-meaningful constraints. In this talk, we present a novel algorithm, called Enhanced Matrix Completion (EMaC), that capitalizes on both sparsity and physically-meaning constraints to recover a spectrally sparse object from random subsampled time domain data. The algorithm starts by arranging the data into a low-rank enhanced form with multi-fold Hankel structure whose rank is upper bounded by the sparsity level, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the sparsity level within logarithm factors, and is robust against bounded and sparse noise. The performance of EMaC and its potential applicability to super resolution are further demonstrated by numerical experiments.


Yuejie Chi received the Ph.D. degree in Electrical Engineering from Princeton University in 2012, and the B.E. (Hon.) degree in Electrical Engineering from Tsinghua University, Beijing, China, in 2007. Since September 2012, she has been an assistant professor with the department of Electrical and Computer Engineering and the department of Biomedical Informatics at the Ohio State University. She has held visiting positions at Colorado State University, Stanford University and Duke University, and interned at Qualcomm Inc. and Mitsubishi Electric Research Lab. She received the IEEE Signal Processing Society Young Author Best Paper Award in 2013, the Best Paper Award from the International Conference on Acoustics, Speech, and Signal Processing (ICASSP) in 2012. She received a Google Faculty Research Award in 2013, a Roberto Padovani scholarship from Qualcomm Inc. in 2010, and an Engineering Fellowship from Princeton University in 2007. Her research interests include statistical signal processing, machine learning, high-dimensional data analysis, machine learning and their applications in array signal processing, network inference, and bioinformatics.