OPTIMAL DETECTION OF SPARSE PRINCIPAL COMPONENTS IN HIGH DIMENSION

被引：151

作者：

Berthet, Quentin ^{[1
]}

Rigollet, Philippe ^{[1
]}

机构：

[1] Princeton Univ, Dept Operat Res & Financial Engn, Princeton, NJ 08544 USA

来源：

ANNALS OF STATISTICS | 2013年 / 41卷 / 04期

基金：

美国国家科学基金会;

关键词：

High-dimensional detection; sparse principal component analysis; spiked covariance model; semidefinite relaxation; minimax lower bounds; planted clique; LARGE HIDDEN CLIQUE; LARGEST EIGENVALUE; NORM; SIZE; PCA; SUBMATRICES; RELAXATIONS; CONSISTENCY; MATRICES; NOISY;

D O I：

10.1214/13-AOS1127

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels, and it performs well on simulated datasets. Moreover, using polynomial time reductions from theoretical computer science, we bring significant evidence that our results cannot be improved, thus revealing an inherent trade off between statistical and computational performance.

引用

页码：1780 / 1815

页数：36

共 76 条

[11] DETECTION OF CORRELATIONS [J].

Arias-Castro, Ery ;

Bubeck, Sebastien ;

Lugosi, Gabor .

ANNALS OF STATISTICS, 2012, 40 (01) :412-435

[12] GLOBAL TESTING UNDER SPARSE ALTERNATIVES: ANOVA, MULTIPLE COMPARISONS AND THE HIGHER CRITICISM [J].

Arias-Castro, Ery ;

Candes, Emmanuel J. ;

Plan, Yaniv .

ANNALS OF STATISTICS, 2011, 39 (05) :2533-2556

[13] DETECTION OF AN ANOMALOUS CLUSTER IN A NETWORK [J].

Arias-Castro, Ery ;

Candes, Emmanuel J. ;

Durand, Arnaud .

ANNALS OF STATISTICS, 2011, 39 (01) :278-304

[14]

Bach Francis., 2010, PREPRINT

[15]

Bai ZD, 1999, STAT SINICA, V9, P611

[16] Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices [J].

Baik, J ;

Ben Arous, G ;

Péché, S .

ANNALS OF PROBABILITY, 2005, 33 (05) :1643-1697

[17] Eigenvalues of large sample covariance matrices of spiked population models [J].

Baik, Jinho ;

Silverstein, Jack W. .

JOURNAL OF MULTIVARIATE ANALYSIS, 2006, 97 (06) :1382-1408

[18]

BANDEIRA A. S., 2012, PREPRINT

[19]

Baraud Y, 2002, BERNOULLI, V8, P577

[20] COVARIANCE REGULARIZATION BY THRESHOLDING [J].

Bickel, Peter J. ;

Levina, Elizaveta .

ANNALS OF STATISTICS, 2008, 36 (06) :2577-2604

← 1 2 3 4 5 6 7 8 →