Skip to main content
SpringerLink
Log in

Random Laplacian Matrices and Convex Relaxations

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

The largest eigenvalue of a matrix is always larger or equal than its largest diagonal entry. We show that for a class of random Laplacian matrices with independent off-diagonal entries, this bound is essentially tight: the largest eigenvalue is, up to lower order terms, often the size of the largest diagonal. entry. Besides being a simple tool to obtain precise estimates on the largest eigenvalue of a class of random Laplacian matrices, our main result settles a number of open problems related to the tightness of certain convex relaxation-based algorithms. It easily implies the optimality of the semidefinite relaxation approaches to problems such as \({{\mathbb {Z}}}_2\) Synchronization and stochastic block model recovery. Interestingly, this result readily implies the connectivity threshold for Erdős–Rényi graphs and suggests that these three phenomena are manifestations of the same underlying principle. The main tool is a recent estimate on the spectral norm of matrices with independent entries by van Handel and the author.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Our results will be of nonasymptotic nature (we refer the interested reader to [47] for a tutorial on nonasymptotic estimates in random matrix theory).

  2. The Erdős–Rényi model for random graphs will be discussed in more detail in Sect. 3.1.

  3. This will be done by considering a centered version of the Laplacian of the random graph, and relating also the spectral properties and diagonal of it to the ones of the original Laplacian.

  4. The information-theoretic limits of this problem have also been investigated [1, 2, 15, 16].

  5. When the optimal solution of a semidefinite relaxation is the optimal solution of the original problem, we say that the relaxation is tight.

  6. While the result in this section is not a direct application of Theorem 2.1, it will help providing intuition of how Theorem 2.1 plays a crucial role in the estimates in the next sections.

  7. The diagonal entries of \(D_W\) are not independent because each pair of sums shares a term \(W_{ij}\) as a summand.

  8. While a simple adaptation of the proof of Theorem 2.1 can establish (13) and (14) we omit their proofs for the sake of brevity, but emphasize that in this particular setting (where W is a standard Wigner matrix), one does not need the whole strength of Theorem 2.1 as more elementary proofs exist.

  9. Recall that, if we assume a uniform prior, the MLE is the method that maximizes the probability of exact recovery.

  10. One can build such a cut by consecutively selecting memberships for each node in a greedy fashion as to maximize the number of incident edges cut, see [41].

  11. For the particular example of connectivity of an Erdős–Rényi graph, it is possible to use the matrix concentration approach [44, 45] to obtain a guarantee that, while being a factor away from optimal, appears to be adaptable to instances where edges have particular types of dependencies—we refer the reader to Sect. 5.3. in the monograph [45].

References

  1. E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer. Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery. Network Science and Engineering, IEEE Transactions on, 1(1):10–22, Jan 2014.

    Article  MathSciNet  Google Scholar 

  2. E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer. Linear inverse problems on Erdős-Rényi graphs: Information-theoretic limits and efficient recovery. IEEE International Symposium on Information Theory (ISIT2014), 2014.

  3. E. Abbe, A. . Bandeira, and G. Hall. Exact recovery in the stochastic block model. Available online at arXiv:1405.3267v4 [cs.SI], 2014.

  4. N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla. Multisection in the stochastic block model using semidefinite programming. Available online at arXiv:1507.02323 [cs.DS], 2015.

  5. F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5:13–51, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  6. G. W. Anderson, A. Guionnet, and O. Zeitouni. An introduction to random matrices. Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, New York, Melbourne, 2010.

    MATH  Google Scholar 

  7. A. S. Bandeira, N. Boumal, and A. Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Available online at arXiv:1411.3272 [math.OC], 2014.

  8. A. S. Bandeira, Y. Khoo, and A. Singer. Open problem: Tightness of maximum likelihood semidefinite relaxations. In Proceedings of the 27th Conference on Learning Theory, volume 35 of JMLR W&CP, pages 1265–1267, 2014.

  9. A. S. Bandeira, A. Singer, and D. A. Spielman. A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl., 34(4):1611–1630, 2013.

    Article  MathSciNet  MATH  Google Scholar 

  10. A. S. Bandeira and R. v. Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Annals of Probability, to appear, 2015.

  11. N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3):89–113, 2004.

    Article  MathSciNet  MATH  Google Scholar 

  12. R. B. Boppana. Eigenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium on Foundations of Computer Science, pages 280–285, 1987.

  13. S. Boucheron, O. Bousquet, G. Lugosi, and P. Massart. Moment inequalities for functions of independent random variables. Ann. Probab., 33(2):514–560, 2005.

    Article  MathSciNet  MATH  Google Scholar 

  14. W. Bryc, A. Dembo, and T. Jiang. Spectral measure of large random Hankel, Markov and Toeplitz matrices. The Annals of Probability, 34(1):pp. 1–38, 2006.

    Article  MathSciNet  MATH  Google Scholar 

  15. Y. Chen and A. J. Goldsmith. Information recovery from pairwise measurements. IEEE International Symposium on Information Theory (ISIT2014), 2014.

  16. Y. Chen, C. Suh, and A. J. Goldsmith. Information recovery from pairwise measurements: A Shannon-theoretic approach. Available online at arXiv:1504.01369 [cs.IT], 2015.

  17. F. Chung and L. Lu. Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics). American Mathematical Society, Boston, MA, USA, 2006.

    Google Scholar 

  18. F. R. K. Chung. Spectral Graph Theory. AMS, 1997.

  19. M. Cucuringu. Synchronization over Z2 and community detection in signed multiplex networks with constraints. Journal of Complex Networks, 2015.

  20. K. Davidson and S. Szarek. Local operator theory, random matrices and Banach spaces. In Handbook on the Geometry of Banach spaces, volume 1, pages 317–366. Elsevier Science, 2001.

  21. A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84, December 2011.

  22. X. Ding and T. Jiang. Spectral distribution of adjacency and Laplacian matrices of random graphs. The Annals of Applied Probability, 20(6):2086–2117, 2010.

    Article  MathSciNet  MATH  Google Scholar 

  23. R. Durrett. Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics). Cambridge University Press, New York, NY, USA, 2006.

    Book  Google Scholar 

  24. P. Erdős and A. Rényi. On random graphs, I. Publicationes Mathematicae (Debrecen), 6:290–297, 1959.

    MATH  Google Scholar 

  25. U. Feige and J. Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639 – 671, 2001.

    Article  MathSciNet  MATH  Google Scholar 

  26. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefine programming. Journal of the Association for Computing Machinery, 42:1115–1145, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  27. M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981.

    Article  MathSciNet  MATH  Google Scholar 

  28. B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming. Available online at arXiv:1412.6156, 2014.

  29. B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming: Extensions. Available online at arXiv:1502.07738, 2015.

  30. S. Khot. On the power of unique 2-prover 1-round games. Thiry-fourth annual ACM symposium on Theory of computing, 2002.

  31. M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991.

  32. L. Lovasz. On the shannon capacity of a graph. IEEE Trans. Inf. Theor., 25(1):1–7, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  33. P. Massart. About the constants in Talagrand’s concentration inequalities for empirical processes. The Annals of Probability, 28(2), 2000.

  34. L. Massoulié. Community detection thresholds and the weak Ramanujan property. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 694–703, New York, NY, USA, 2014. ACM.

  35. F. McSherry. Spectral partitioning of random graphs.

  36. E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for the planted bisection model. Available online at arXiv:1407.1591v2 [math.PR], July 2014.

  37. E. Mossel, J. Neeman, and A. Sly. A proof of the block model threshold conjecture. Available online at arXiv:1311.4115 [math.PR], January 2014.

  38. E. Mossel, J. Neeman, and A. Sly. Stochastic block models and reconstruction. Probability Theory and Related Fields (to appear), 2014.

  39. Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994.

  40. P. Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 245–254. ACM, 2008.

  41. S. Sahni and T. Gonzalez. P-complete approximation problems. J. ACM, 23(3):555–565, July 1976.

    Article  MathSciNet  MATH  Google Scholar 

  42. A. Singer. Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal., 30(1):20 – 36, 2011.

    Article  MathSciNet  MATH  Google Scholar 

  43. T. Tao. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Soc., 2012.

  44. J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012.

    Article  MathSciNet  MATH  Google Scholar 

  45. J. A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learning, 8(1–2):1–230, 2015.

    Article  MATH  Google Scholar 

  46. L. Vanderberghe and S. Boyd. Semidefinite programming. SIAM Review, 38:49–95, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  47. R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. Chapter 5 of: Compressed Sensing, Theory and Applications. Edited by Y. Eldar and G. Kutyniok. Cambridge University Press, 2012.

  48. E. P. Wigner. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics, 67(2):pp. 325–327, 1958.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author acknowledges Amit Singer, Emmanuel Abbe, Ramon van Handel, and Georgina Hall for many insightful discussions on the topic of this paper and, specially, for motivating the author to write this manuscript. Many thanks to Ramon van Handel for his crucial help locating the references for the strongest version of the theorems used in the proof of our main results. The author is also indebted to Amit Singer, Ramon van Handel, Dustin G. Mixon, Nicolas Boumal, and Joel Tropp for valuable comments on early drafts of this manuscript. The author presented most of these results in various seminars throughout the end of 2014 and beginning of 2015. Many questions and comments raised by the audience greatly improved the quality of this manuscript, a warm thanks to all of them. The author also thanks the anonymous referees for many helpful comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics and Center for Data Science, Courant Institute of Mathematical Sciences, New York University, New York, NY, USA

    Afonso S. Bandeira

Authors
  1. Afonso S. Bandeira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Afonso S. Bandeira.

Additional information

Communicated by Emmanuel Jean Candés.

Most of this work was carried out, while the author was with the Program in Applied and Computational Mathematics in Princeton University and supported by AFOSR Grant No. FA9550-12-1-0317. Part of the work was also done with the author was with the Department of Mathematics at the Massachusetts Institute of Technology and supported by NSF Grant DMS-1317308.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bandeira, A.S. Random Laplacian Matrices and Convex Relaxations. Found Comput Math 18, 345–379 (2018). https://doi.org/10.1007/s10208-016-9341-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-016-9341-9

Keywords

Mathematics Subject Classification

Search

Navigation