All Publications


  • Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization OPERATIONS RESEARCH Cen, S., Cheng, C., Chen, Y., Wei, Y., Chi, Y. 2021
  • Tackling Small Eigen-Gaps: Fine-Grained Eigenvector Estimation and Inference Under Heteroscedastic Noise IEEE TRANSACTIONS ON INFORMATION THEORY Cheng, C., Wei, Y., Chen, Y. 2021; 67 (11): 7380-7419
  • ASYMMETRY HELPS: EIGENVALUE AND EIGENVECTOR ANALYSES OF ASYMMETRICALLY PERTURBED LOW-RANK MATRICES. Annals of statistics Chen, Y., Cheng, C., Fan, J. 2021; 49 (1): 435-458

    Abstract

    This paper is concerned with the interplay between statistical asymmetry and spectral methods. Suppose we are interested in estimating a rank-1 and symmetric matrix M ⋆ ∈ ℝ n × n , yet only a randomly perturbed version M is observed. The noise matrix M - M ⋆ is composed of independent (but not necessarily homoscedastic) entries and is, therefore, not symmetric in general. This might arise if, for example, we have two independent samples for each entry of M ⋆ and arrange them in an asymmetric fashion. The aim is to estimate the leading eigenvalue and the leading eigenvector of M ⋆. We demonstrate that the leading eigenvalue of the data matrix M can be O ( n ) times more accurate (up to some log factor) than its (unadjusted) leading singular value of M in eigenvalue estimation. Moreover, the eigen-decomposition approach is fully adaptive to heteroscedasticity of noise, without the need of any prior knowledge about the noise distributions. In a nutshell, this curious phenomenon arises since the statistical asymmetry automatically mitigates the bias of the eigenvalue approach, thus eliminating the need of careful bias correction. Additionally, we develop appealing non-asymptotic eigenvector perturbation bounds; in particular, we are able to bound the perterbation of any linear function of the leading eigenvector of M (e.g. entrywise eigenvector perturbation). We also provide partial theory for the more general rank-r case. The takeaway message is this: arranging the data samples in an asymmetric manner and performing eigen-decomposition could sometimes be quite beneficial.

    View details for DOI 10.1214/20-aos1963

    View details for PubMedID 34305194

    View details for PubMedCentralID PMC8300484