On the sample complexity of multichannel frequency estimation via convex optimization

The use of multichannel data in line spectral estimation (or frequency estimation) is common for improving the estimation accuracy in array processing, structural health monitoring, wireless communications, and more. Recently proposed atomic norm methods have attracted considerable attention due to their provable superiority in accuracy, flexibility, and robustness compared with conventional approaches. In this paper, we analyze atomic norm minimization for multichannel frequency estimation from noiseless compressive data, showing that the sample size per channel that ensures exact estimation decreases with the increase of the number of channels under mild conditions. In particular, given L channels, order K (log K) (1 + L/1 log N) samples per channel, selected randomly from N equispaced samples, suffice to ensure with high probability exact estimation of K frequencies that are normalized and mutually separated by at least 4/N. Numerical results are provided corroborating our analysis.Ministry of Education (MOE)Accepted versionThis was supported in part by the National Natural Science Foundation of China under Grants 61603187, 61772275, and 61732007, in part by the Natural Science Foundation of Jiangsu Province, China, under Grant BK20160845, in part by the Israel Science Foundation under Grant 0100101, and in part by the Ministry of Education, Republic of Singapore, under Grant AcRF TIER 1 RG78/15