2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | E.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
