Fetching the paper…
Reading the bibliography…
In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency.
Persi Diaconis and David Freedman, Finite exchangeable sequences , Ann. Probab. 8
1980
Earlier work this paper cites.
Ravi B. Boppana, Eigenvalues and graph bisection: An average-case analysis , Foundations of Computer Science, 1987., 28th Annual Symposium on, oct. 1987, pp. 280 –285
1987
Earlier work this paper cites.
Mark Jerrum, Large cliques elude the Metropolis process , Random Structures Algorithms 3
1992
Earlier work this paper cites.
Luděk Kučera, Expected complexity of graph partitioning problems , Discrete Appl. Math. 57
1992
Earlier work this paper cites.
Joel Spencer, Ten lectures on the probabilistic method , second ed., CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 64, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. MR1249485 (95c:05113)
1994
Earlier work this paper cites.
Johan Håstad, Clique is hard to approximate within n 1 − ϵ n^{1-\epsilon} , 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 627–636. MR1450661
1996
Earlier work this paper cites.
Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a random graph , Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (Philadelphia, PA, USA), SODA ’98, Society for Industrial and Applied Mathematics, 1998, pp. 594–598
1998
Earlier work this paper cites.
Richard Dudley, Uniform central limit theorems , Cambridge University Press, 1999
1999
Earlier work this paper cites.
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph , Random Structures Algorithms 16
2000
Earlier work this paper cites.
Ari Juels and Marcus Peinado, Hiding cliques for cryptographic security , Des. Codes Cryptogr. 20
2000
Earlier work this paper cites.
Frank McSherry, Spectral partitioning of random graphs , 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 529–537. MR1948742
2001
Earlier work this paper cites.
Michael Krivelevich and Van H. Vu, Approximating the independence number and the chromatic number in expected polynomial time , J. Comb. Optim. 6
2002
Earlier work this paper cites.
Pascal Massart, Concentration inequalities and model selection , Lecture Notes in Mathematics, vol. 1896, Springer, Berlin, 2007, Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003, With a foreword by Jean Picard. MR2319879
2003
Earlier work this paper cites.
Stephen Boyd and Lieven Vandenberghe, Convex optimization , Cambridge University Press, Cambridge, 2004. MR2061575 (2005d:90002)
2004
Earlier work this paper cites.
Alexandre B. Tsybakov, Introduction to nonparametric estimation , Springer Series in Statistics, Springer, New York, 2009, Revised and extended from the 2004 French original, Translated by Vladimir Zaiats. MR2724359 (2011g:62006)
2004
Earlier work this paper cites.
David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number , Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (New York, NY, USA), STOC ’06, ACM, 2006, pp. 681–690
2006
Cited alongside, same era.
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie, Testing k k -wise and almost k k -wise independence , STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 496–505. MR2402475 (2010a:68181)
2007
Cited alongside, same era.
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet, A direct formulation for sparse PCA using semidefinite programming , SIAM Review 49
2007
Cited alongside, same era.
Arash A. Amini and Martin J. Wainwright, High-dimensional analysis of semidefinite relaxations for sparse principal components , Annals of Statistics 37
2009
Cited alongside, same era.
Elad Hazan and Robert Krauthgamer, How hard is it to approximate the best nash equilibrium? , SIAM J. Comput. 40
2011
Later among the works it cites.
M. Kolar, S. Balakrishnan, A. Rinaldo, and A. Singh, Minimax localization of structural information in large noisy matrices , Advances in Neural Information Processing Systems (2011)
2011
Later among the works it cites.
Ery Arias-Castro, Sébastien Bubeck, and Gábor Lugosi, Detection of correlations , Ann. Statist. 40
2012
Later among the works it cites.
2012
Later among the works it cites.
T. Tony Cai, Zongming Ma, and Yihong Wu, Sparse PCA: Optimal rates and adaptive estimation , Arxiv Preprint (2012)
2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Iain M. Johnstone and Arthur Yu Lu, On consistency and sparsity for principal components analysis in high dimensions , J. Amer. Statist. Assoc. 104
2009
Cited alongside, same era.
Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and Gábor Lugosi, On combinatorial testing problems , Annals of Statistics 38
2010
Cited alongside, same era.
Francis Bach, Selin Damla Ahipasaoglu, and Alexandre d’Aspremont, Convex relaxations for subset selection , Arxiv Preprint (2010)
2010
Cited alongside, same era.
Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres, Finding hidden cliques in linear time with high probability , Arxiv Preprint (2010)
2010
Cited alongside, same era.
Uriel Feige and Dorit Ron, Finding hidden cliques in linear time , 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’10), Discrete Math. Theor. Comput. Sci. Proc., AM, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010, pp. 189–203. MR2735341 (2012b:05192)
2010
Cited alongside, same era.
Benjamin Rossman, Average-Case Complexity of Detecting Cliques , ProQuest LLC, Ann Arbor, MI, 2010, Thesis (Ph.D.)–Massachusetts Institute of Technology. MR2873600
2010
Cited alongside, same era.
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices , Arxiv Preprint (2010)
2010
Cited alongside, same era.
Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein, On the inapproximability of the densest κ \kappa -subgraph problem , Unpublished, April 2011
2011
Cited alongside, same era.
2012
Later among the works it cites.
Shai Shalev-Shwartz, Ohad Shamir, and Eran Tomer, Using more data to speed-up training time , Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics April 21-23, 2012 La Palma, Canary Islands., JMLR W&CP, vol. 22, 2012, pp. 1019–1027
2012
Later among the works it cites.
Vincent Vu and Jing Lei, Minimax rates of estimation for sparse pca in high dimensions , Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics April 21-23, 2012 La Palma, Canary Islands., JMLR W&CP, vol. 22, 2012, pp. 1278–1286
2012
Later among the works it cites.
2013
Closest in time.
Ery Arias-Castro and Nicolas Verzelen, Community detection in random networks , Arxiv Preprint (2013)
2013
Closest in time.
Cristina Butucea and Yuri I. Ingster, Detection of a sparse submatrix of a high-dimensional noisy matrix , Bernoulli (to appear) (2013)
2013
Closest in time.
Venkat Chandrasekaran and Michael I. Jordan, Computational and statistical tradeoffs via convex relaxation , Proceedings of the National Academy of Sciences (2013)
2013
Closest in time.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao, Statistical algorithms and a lower bound for planted clique , Proceedings of the Fourty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, 2013
2013
Closest in time.
Zongming Ma, Sparse principal component analysis and iterative thresholding , Ann. Statist. (to appear) (2013)
2013
Closest in time.
Xing Sun and Andrew B. Nobel, On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix. , Bernoulli 19
2013
Closest in time.