Technical Program

Paper Detail

Paper IDE.3.2
Paper Title On the Sample Complexity of Estimating Small Singular Modes
Authors Xiangxiang Xu, Tsinghua University, China; Weida Wang, Shao-Lun Huang, Tsinghua-Berkeley Shenzhen Institute, China
Session E.3: Estimation Theory
Presentation Lecture
Track Detection and Estimation
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract While it is commonly believed that estimating the small singular modes for a nearly low-rank matrix requires more samples, the sample size needed is generally unclear. In this paper, we investigate this sample complexity by considering the difference between the estimation errors of estimating a matrix with or without estimating these small singular modes. Specifically, we develop a mathematical framework based on the matrix perturbation analysis to characterize the noise level of estimating small singular modes by $n$ samples. In particular, we show that under mild assumptions on the sample noise, it requires at least $n = O(\eta^{-2})$ samples to well estimate the singular modes with the singular value in the order of some small $\eta$. More importantly, our results are applied to the channel state estimation and Hirschfeld-Gebelein-R\'{e}nyi (HGR) maximal correlation problems, from which we characterize that for how many samples, utilizing the low-rank approximation in these problems are beneficial. Finally, numerical simulations are provided to verify our results.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!