Optimal detection of sparse principal components in high dimension

Karp, Richard M.R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) 85–103. Plenum, New York

1972

Earlier work this paper cites.

Geman, StuartS. (1980). A limit theorem for the norm of random matrices. Ann. Probab. 8 252–261

1980

Earlier work this paper cites.

Ingster, Yu. I.Y. I. (1982). The asymptotic efficiency of tests for a simple hypothesis against a composite alternative. Teor. Veroyatn. Primen. 27 587–592

1982

Earlier work this paper cites.

Nesterov, Y.Y. andNemirovskii, A.A. (1987). Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial Mathematics 13. SIAM, Philadelphia, PA

1987

Earlier work this paper cites.

Yin, Y. Q.Y. Q., Bai, Z. D.Z. D. andKrishnaiah, P. R.P. R. (1988). On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix. Probab. Theory Related Fields 78 509–521

1988

Earlier work this paper cites.

Jerrum, MarkM. (1992). Large cliques elude the Metropolis process. Random Structures Algorithms 3 347–359

1992

Earlier work this paper cites.

Spencer, JoelJ. (1994). Ten Lectures on the Probabilistic Method, 2nd ed. CBMS-NSF Regional Conference Series in Applied Mathematics 64. SIAM, Philadelphia, PA

1994

Earlier work this paper cites.

Goemans, Michel X.M. X. andWilliamson, David P.D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 1115–1145

1995

Earlier work this paper cites.

Kučera, LuděkL. (1995). Expected complexity of graph partitioning problems. Discrete Appl. Math. 57 193–212

1995

Earlier work this paper cites.

Alon, NogaN., Krivelevich, MichaelM. andSudakov, BennyB. (1998). Finding a large hidden clique in a random graph. Random Structures Algorithms 13 457–466

1998

Earlier work this paper cites.

Alon, U.U., Barkai, N.N., Notterman, D. A.D. A., Gish, K.K., Ybarra, S.S., Mack, D.D. andLevine, A. J.A. J. (1999). Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Proc. Natl. Acad. Sci. USA 96 6745–6750

1999

Earlier work this paper cites.

Bai, Z. D.Z. D. (1999). Methodologies in spectral analysis of large-dimensional random matrices, a review. Statist. Sinica 9 611–677

1999

Earlier work this paper cites.

Feige, UrielU. andKrauthgamer, RobertR. (2000). Finding and certifying a large hidden clique in a semirandom graph. Random Structures Algorithms 16 195–208

2000

Earlier work this paper cites.

Juels, AriA. andPeinado, MarcusM. (2000). Hiding cliques for cryptographic security. Des. Codes Cryptogr. 20 269–280

2000

Earlier work this paper cites.

Laurent, B.B. andMassart, P.P. (2000). Adaptive estimation of a quadratic functional by model selection. Ann. Statist. 28 1302–1338

2000

Earlier work this paper cites.

Johnstone, Iain M.I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist. 29 295–327

2001

Earlier work this paper cites.

Baraud, YannickY. (2002). Non-asymptotic minimax rates of testing in signal detection. Bernoulli 8 577–606

2002

Earlier work this paper cites.

Krivelevich, MichaelM. andVu, Van H.V. H. (2002). Approximating the independence number and the chromatic number in expected polynomial time. J. Comb. Optim. 6 143–155

2002

Earlier work this paper cites.

Feige, UrielU. andKrauthgamer, RobertR. (2003). The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM J. Comput. 32 345–370 (electronic)

2003

Earlier work this paper cites.

Nesterov, YuriiY. (2003). Introductory Lectures on Convex Optimization. Springer, New York

2003

Earlier work this paper cites.

Boyd, StephenS. andVandenberghe, LievenL. (2004). Convex Optimization. Cambridge Univ. Press, Cambridge

2004

Earlier work this paper cites.

Donoho, DavidD. andJin, JiashunJ. (2004). Higher criticism for detecting sparse heterogeneous mixtures. Ann. Statist. 32 962–994

2004

Earlier work this paper cites.

Tsybakov, Alexandre B.A. B. (2009). Introduction to Nonparametric Estimation. Springer, New York. Revised and extended from the 2004 French original, translated by Vladimir Zaiats

2004

Earlier work this paper cites.

Baik, JinhoJ., Ben Arous, GérardG. andPéché, SandrineS. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab. 33 1643–1697

2005

Earlier work this paper cites.

Baik, JinhoJ. andSilverstein, Jack W.J. W. (2006). Eigenvalues of large sample covariance matrices of spiked population models. J. Multivariate Anal. 97 1382–1408

2006

Earlier work this paper cites.

Alon, NogaN., Andoni, AlexandrA., Kaufman, TaliT., Matulef, KevinK., Rubinfeld, RonittR. andXie, NingN. (2007). Testing k k -wise and almost k k -wise independence. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing 496–505. ACM, New York

2007

Cited alongside, same era.

d’Aspremont, AlexandreA., El Ghaoui, LaurentL., Jordan, Michael I.M. I. andLanckriet, Gert R. G.G. R. G. (2007). A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49 434–448 (electronic)

2007

Cited alongside, same era.

Paul, DebashisD. (2007). Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statist. Sinica 17 1617–1642

2007

Cited alongside, same era.

Bickel, Peter J.P. J. andLevina, ElizavetaE. (2008). Covariance regularization by thresholding. Ann. Statist. 36 2577–2604

2008

Cited alongside, same era.

Chen, XiX. (2011). Adaptive elastic-net sparse principal component analysis for pathway association testing. Stat. Appl. Genet. Mol. Biol. 10 Art. 48, 23

2011

Later among the works it cites.

Dekel, YaelY., Gurel-Gurevich, OriO. andPeres, YuvalY. (2011). Finding hidden cliques in linear time with high probability. In ANALCO11—Workshop on Analytic Algorithmics and Combinatorics 67–75. SIAM, Philadelphia, PA

2011

Later among the works it cites.

Hazan, EladE. andKrauthgamer, RobertR. (2011). How hard is it to approximate the best Nash equilibrium? SIAM J. Comput. 40 79–91

2011

Later among the works it cites.

Ma, S.S. (2011). Alternating direction method of multipliers for sparse principal component analysis. Preprint. Available at \arxivurl

Original

2011

Later among the works it cites.

Wright, J.J., Ganesh, A.A., Yang, A.A., Zhou, Z.Z. andMa, Y.Y. (2011). Sparsity and robustness in face recognition. Preprint. Available at \arxivurl