数学
主成分分析
特征向量
维数(图论)
协方差矩阵
降维
半定规划
维数之咒
样本量测定
稀疏PCA
协方差
对角线的
应用数学
基质(化学分析)
简单(哲学)
样品(材料)
数学优化
阈值
功能(生物学)
集合(抽象数据类型)
基础(拓扑)
算法
对角矩阵
主对角线
内在维度
正定矩阵
协方差矩阵的估计
极限(数学)
组合数学
随机矩阵
度量(数据仓库)
作者
Arash A. Amini,Martin J. Wainwright
出处
期刊:Annals of Statistics
[Institute of Mathematical Statistics]
日期:2009-07-17
卷期号:37 (5B): 2877-2921
被引量:267
摘要
Principal component analysis (PCA) is a classical method for dimensionality reduction based on extracting the dominant eigenvectors of the sample covariance matrix. However, PCA is well known to behave poorly in the “large p, small n” setting, in which the problem dimension p is comparable to or larger than the sample size n. This paper studies PCA in this high-dimensional regime, but under the additional assumption that the maximal eigenvector is sparse, say, with at most k nonzero components. We consider a spiked covariance model in which a base matrix is perturbed by adding a k-sparse maximal eigenvector, and we analyze two computationally tractable methods for recovering the support set of this maximal eigenvector, as follows: (a) a simple diagonal thresholding method, which transitions from success to failure as a function of the rescaled sample size θdia(n, p, k)=n/[k2log(p−k)]; and (b) a more sophisticated semidefinite programming (SDP) relaxation, which succeeds once the rescaled sample size θsdp(n, p, k)=n/[klog(p−k)] is larger than a critical threshold. In addition, we prove that no method, including the best method which has exponential-time complexity, can succeed in recovering the support if the order parameter θsdp(n, p, k) is below a threshold. Our results thus highlight an interesting trade-off between computational and statistical efficiency in high-dimensional inference.
科研通智能强力驱动
Strongly Powered by AbleSci AI