Spectral norm of random matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spectral norm of random matrices

Full text

Pdf (224 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing table of contents

Baltimore, MD, USA

SESSION: Session 9B table of contents

Pages: 423 - 430

Year of Publication: 2005

ISBN:1-58113-960-8

Author

V. H. Vu

UCSD, La Jolla, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 28, Downloads (12 Months): 93, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1060590.1060654 What is a DOI?

ABSTRACT

In this paper, we present a new upper bound for the spectral norm of symmetric random matrices with independent (but not necessarily identical) entries. Our results improve an earlier result of Füredi and Komlós and also correct an incomplete argument in their proof.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Noga Alon, Spectral Techniques in Graph Algorithms, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.206-215, April 20-24, 1998
	2	N. Alon, M. Krivelevich and V. Vu, On the concentration of eigenvalues of random symmetric matrices, Israel J. Math.131 (2002), 259--267.
	3	FK Z, Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233--241.
	4	M. Krivelevich and V. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Comb. Optim. 6 (2002), no. 2, 143--155.
	5	M. L. Mehta, Random matrices, Second edition. Academic Press, Inc., Boston, MA, 1991.
	6	Y. Sinai and A. Soshnikov, A Refinement of Wigner's Semicircle Law in a Neighborhood of the Spectrum edge, \|it Functional Analysis and its Applications, 32 (1998) , No.2, pp.114--131.
	7	E. Wigner, On the distribution of the roots of certain symmetric matrices, The Annals of Mathematics 67 (1958) 325--327.

CITED BY 3

	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Dimitris Achlioptas , Frank Mcsherry, Fast computation of low-rank matrix approximations, Journal of the ACM (JACM), v.54 n.2, p.9-es, April 2007
	Anirban Dasgupta , John Hopcroft , Ravi Kannan , Pradipta Mitra, Spectral clustering with limited independence, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1036-1045, January 07-09, 2007, New Orleans, Louisiana