References
- Airoldi, E. M., Blei, D. M., Fienberg, S. E., and Xing, E. P. (2008), “Mixed Membership Stochastic Blockmodels,” Journal of Machine Learning Research, 9, 1981–2014.
- Amini, A. A., Chen, A., Bickel, P. J., and Levina, E. (2013), “Pseudo-Likelihood Methods for Community Detection in Large Sparse Networks,” The Annals of Statistics, 41, 2097–2122. DOI: https://doi.org/10.1214/13-AOS1138.
- Amini, A. A., and Levina, E. (2018), “On Semidefinite Relaxations for the Block Model,” The Annals of Statistics, 46, 149–179. DOI: https://doi.org/10.1214/17-AOS1545.
- Balakrishnan, S., Wainwright, M. J., and Yu, B. (2017), “Statistical Guarantees for the EM Algorithm: From Population to Sample-Based Analysis,” The Annals of Statistics, 45, 77–120. DOI: https://doi.org/10.1214/16-AOS1435.
- Binkiewicz, N., Vogelstein, J. T., and Rohe, K. (2017), “Covariate-Assisted Spectral Clustering,” Biometrika, 104, 361–377. DOI: https://doi.org/10.1093/biomet/asx008.
- Braverman, M., Makarychev, K., Makarychev, Y., and Naor, A. (2013), “The Grothendieck Constant Is Strictly Smaller Than Krivine’s Bound,” in Forum of Mathematics, Pi, Cambridge University Press, 1, e4. DOI: https://doi.org/10.1017/fmp.2013.4.
- Burer, S., and Monteiro, R. D. (2003), “A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-Rank Factorization,” Mathematical Programming, 95, 329–357. DOI: https://doi.org/10.1007/s10107-002-0352-8.
- Cai, T. T., and Li, X. (2015), “Robust and Computationally Feasible Community Detection in the Presence of Arbitrary Outlier Nodes,” The Annals of Statistics, 43, 1027–1059. DOI: https://doi.org/10.1214/14-AOS1290.
- Chaudhuri, K., Kakade, S. M., Livescu, K., and Sridharan, K. (2009), “Multi-View Clustering via Canonical Correlation Analysis,” in Proceedings of the 26th Annual International Conference on Machine Learning, ACM, pp. 129–136. DOI: https://doi.org/10.1145/1553374.1553391.
- Chen, C., He, B., Ye, Y., and Yuan, X. (2016), “The Direct Extension of ADMM for Multi-Block Convex Minimization Problems Is Not Necessarily Convergent,” Mathematical Programming, 155, 57–79. DOI: https://doi.org/10.1007/s10107-014-0826-5.
- Chen, Y., and Xu, J. (2016), “Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization With a Growing Number of Clusters and Submatrices,” Journal of Machine Learning Research, 17, 1–57.
- Dasgupta, S., and Schulman, L. (2007), “A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians,” Journal of Machine Learning Research, 8, 203–226.
- El Karoui, N. (2010), “On Information Plus Noise Kernel Random Matrices,” The Annals of Statistics, 38, 3191–3216. DOI: https://doi.org/10.1214/10-AOS801.
- Fares, B., Noll, D., and Apkarian, P. (2002), “Robust Control via Sequential Semidefinite Programming,” SIAM Journal on Control and Optimization, 40, 1791–1820. DOI: https://doi.org/10.1137/S0363012900373483.
- Gil-Mendieta, J., and Schmidt, S. (1996), “The Political Network in Mexico,” Social Networks, 18, 355–381. DOI: https://doi.org/10.1016/0378-8733(95)00281-2.
- Guédon, O., and Vershynin, R. (2015), “Community Detection in Sparse Networks via Grothendieck’s Inequality,” Probability Theory and Related Fields, 165, 1025–1049. DOI: https://doi.org/10.1007/s00440-015-0659-z.
- Hajek, B., Wu, Y., and Xu, J. (2016), “Achieving Exact Cluster Recovery Threshold via Semidefinite Programming,” IEEE Transactions on Information Theory, 62, 2788–2797. DOI: https://doi.org/10.1109/TIT.2016.2546280.
- Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983), “Stochastic Blockmodels: First Steps,” Social Networks, 5, 109–137. DOI: https://doi.org/10.1016/0378-8733(83)90021-7.
- Hsu, D., Kakade, S. M., and Zhang, T. (2012), “A Tail Inequality for Quadratic Forms of Subgaussian Random Vectors,” Electronic Communications in Probability, 17, 1–6. DOI: https://doi.org/10.1214/ECP.v17-2079.
- Jacob, U., Thierry, A., Brose, U., Arntz, W. E., Berg, S., Brey, T., Fetzer, I., Jonsson, T., Mintenbeck, K., Mollmann, C., and Petchey, O. L. (2011), “The Role of Body Size in Complex Food Webs: A Cold Case,” Advances in Ecological Research, 45, 181–223.
- Jin, J., Ke, Z. T., and Wang, W. (2017), “Phase Transitions for High Dimensional Clustering and Related Problems,” The Annals of Statistics, 45, 2151–2189. DOI: https://doi.org/10.1214/16-AOS1522.
- Kumar, A., Rai, P., and Daume, H. (2011), “Co-Regularized Multi-View Spectral Clustering,” in Advances in Neural Information Processing Systems (Vol. 24), pp. 1413–1421.
- Kushagra, S., McNabb, N., Yu, Y., and Ben-David, S. (2017), “Provably Noise-Robust, Regularised k-Means Clustering,” arXiv no. 1711.11247.
- Le, C. M., and Levina, E. (2015), “Estimating the Number of Communities in Networks by Spectral Methods,” arXiv no. 1507.00827.
- Li, G., Qi, L., and Yu, G. (2013), “The Z-Eigenvalues of a Symmetric Tensor and Its Application to Spectral Hypergraph Theory,” Numerical Linear Algebra With Applications, 20, 1001–1029. DOI: https://doi.org/10.1002/nla.1877.
- Liu, J., Wang, C., Gao, J., and Han, J. (2013), “Multi-View Clustering via Joint Nonnegative Matrix Factorization,” in Proceedings of the 2013 SIAM International Conference on Data Mining, SIAM, pp. 252–260. DOI: https://doi.org/10.1137/1.9781611972832.28.
- Mixon, D. G., Villar, S., and Ward, R. (2017), “Clustering Subgaussian Mixtures by Semidefinite Programming,” Information and Inference, 6, 389–415. DOI: https://doi.org/10.1093/imaiai/iax001.
- Montanari, A., and Sen, S. (2016), “Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection,” in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, pp. 814–827. DOI: https://doi.org/10.1145/2897518.2897548.
- Monteiro, R. D. C., and Zanjcomo, P. (1999), “Implementation of Primal-Dual Methods for Semidefinite Programming Based on Monteiro and Tsuchiya Newton Directions and Their Variants,” Optimization Methods and Software, 11, 91–140. DOI: https://doi.org/10.1080/10556789908805749.
- Monteiro, R. D., Ortiz, C., and Svaiter, B. F. (2014), “A First-Order Block-Decomposition Method for Solving Two-Easy-Block Structured Semidefinite Programs,” Mathematical Programming Computation, 6, 103–150. DOI: https://doi.org/10.1007/s12532-013-0062-7.
- Mukherjee, S., Sarkar, P., and Bickel, P. (2017), “Two Provably Consistent Divide and Conquer Clustering Algorithms for Large Networks,” arXiv no. 1708.05573.
- Newman, M. E., and Clauset, A. (2016), “Structure and Inference in Annotated Networks,” Nature Communications, 7, 11863. DOI: https://doi.org/10.1038/ncomms11863.
- Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., and Parrilo, P. A. (2013), “SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB,” arXiv no. 1310.4716, available at http://www.eng.ox.ac.uk/control/sostools, http://www.cds.caltech.edu/sostools, and http://www.mit.edu/parrilo/sostools.
- Peng, J., and Wei, Y. (2007), “Approximating k-Means-Type Clustering via Semidefinite Programming,” SIAM Journal on Optimization, 18, 186–205. DOI: https://doi.org/10.1137/050641983.
- Perry, A., and Wein, A. S. (2017), “A Semidefinite Program for Unbalanced Multisection in the Stochastic Block Model,” in International Conference on Sampling Theory and Applications, pp. 64–67.
- Rauhut, H., and Stojanac, Ž. (2015), “Tensor Theta Norms and Low Rank Recovery,” arXiv no. 1505.05175.
- Renegar, J. (2014), “Efficient First-Order Methods for Linear Programming and Semidefinite Programming,” arXiv no. 1409.5832. DOI: https://doi.org/10.1007/s10107-017-1203-y.
- Rohe, K., Chatterjee, S., and Yu, B. (2011), “Spectral Clustering and the High-Dimensional Stochastic Blockmodel,” The Annals of Statistics, 39, 1878–1915. DOI: https://doi.org/10.1214/11-AOS887.
- Shi, T., Belkin, M., and Yu, B. (2009), “Data Spectroscopy: Eigenspaces of Convolution Operators and Clustering,” The Annals of Statistics, 37, 3960–3984. DOI: https://doi.org/10.1214/09-AOS700.
- Sun, D., Toh, K.-C., and Yang, L. (2014), “A Convergent Proximal Alternating Direction Method of Multipliers for Conic Programming With 4-Block Constraints,” Technical Report.
- Vandenberghe, L., and Boyd, S. (1996), “Semidefinite Programming,” SIAM Review, 38, 49–95. DOI: https://doi.org/10.1137/1038003.
- Vempala, S., and Wang, G. (2004), “A Spectral Algorithm for Learning Mixture Models,” Journal of Computer and System Sciences, 68, 841–860. DOI: https://doi.org/10.1016/j.jcss.2003.11.008.
- Verzelen, N., and Arias-Castro, E. (2017), “Detection and Feature Selection in Sparse Mixture Models,” The Annals of Statistics, 45, 1920–1950. DOI: https://doi.org/10.1214/16-AOS1513.
- Villar, S., Bandeira, A. S., Blumberg, A. J., and Ward, R. (2016), “A Polynomial-Time Relaxation of the Gromov-Hausdorff Distance,” arXiv no. 1610.05214.
- Wainwright, M. (2015), “Basic Tail and Concentration Bounds,” available at https://www.stat.berkeley.edu/Chap2/_TailBounds/_Jan22/_2015.pdf.
- Wen, Z., Goldfarb, D., and Yin, W. (2010), “Alternating Direction Augmented Lagrangian Methods for Semidefinite Programming,” Mathematical Programming Computation, 2, 203–230. DOI: https://doi.org/10.1007/s12532-010-0017-1.
- Weng, H., and Feng, Y. (2016), “Community Detection With Nodal Information,” arXiv no. 1610.09735.
- Yan, B., and Sarkar, P. (2016), “On Robustness of Kernel Clustering,” in Advances in Neural Information Processing Systems, pp. 3098–3106.
- Yan, B., Sarkar, P., and Cheng, X. (2018), “Provable Estimation of the Number of Blocks in Block Models,” in Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, PMLR (Vol. 84), pp. 1185–1194.
- Yan, B., Yin, M., and Sarkar, P. (2017), “Convergence of Gradient EM on Multi-Component Mixture of Gaussians,” in Advances in Neural Information Processing Systems, pp. 6959–6969.
- Yang, L., Sun, D., and Toh, K.-C. (2015), “SDPNAL++: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming With Nonnegative Constraints,” Mathematical Programming Computation, 7, 331–366. DOI: https://doi.org/10.1007/s12532-015-0082-6.
- Zhang, Y., Chen, K., Sampson, A., Hwang, K., and Luna, B. (2017), “Node Features Adjusted Stochastic Block Model,” Technical Report, Working Paper.
- Zhang, Y., Levina, E., and Zhu, J. (2016), “Community Detection in Networks With Node Features,” Electronic Journal of Statistics, 10, 3153–3178. DOI: https://doi.org/10.1214/16-EJS1206.
- Zheng, Q., and Lafferty, J. (2015), “A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming From Random Linear Measurements,” in Advances in Neural Information Processing Systems, pp. 109–117.