Norms of random matrices: local and global problems

DOI10.1016/J.AIM.2017.11.001MaRDI QIDQ1684656zbMATHOpenAlexFDO

Authors Elizaveta Rebrova, Roman Vershynin

Publication date 12 December 2017

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06953

zbMATH Keywords

heavy tailsrandom matricesoperator normBai-Yin law

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20)

Abstract: Can the behavior of a random matrix be improved by modifying a small fraction of its entries? Consider a random matrix $A$ with i.i.d. entries. We show that the operator norm of $A$ can be reduced to the optimal order $O(sqrtn)$ by zeroing out a small submatrix of $A$ if and only if the entries have zero mean and finite variance. Moreover, we obtain an almost optimal dependence between the size of the removed submatrix and the resulting operator norm. Our approach utilizes the cut norm and Grothendieck-Pietsch factorization for matrices, and it combines the methods developed recently by C. Le and R. Vershynin and by E. Rebrova and K. Tikhomirov.

Recommendations

• Constructive regularization of the random matrix norm
• Optimal and algorithmic norm regularization of random matrices
• Norms of randomized circulant matrices
• Invertibility of random matrices: norm of the inverse
• On the expectation of operator norms of random matrices

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• An introduction to matrix concentration inequalities
• Approximating the Cut-Norm via Grothendieck's Inequality
• Concentration and regularization of random graphs
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Extreme eigenvalues of sparse, heavy tailed random matrices
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• On the spectral norm of Gaussian random matrices
• On the weak limit of the largest eigenvalue of a large dimensional sample covariance matrix
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Some estimates of norms of random matrices
• Spectral norm of random matrices
• Spectral techniques applied to sparse random graphs
• Structured random matrices
• The Expected Norm of Random Matrices
• The cut metric, random graphs, and branching processes

Cited in

(7)

• Sparse random tensors: concentration, regularization and applications
• Outliers in spectrum of sparse Wigner matrices
• Constructive regularization of the random matrix norm
• Norms on complex matrices induced by random vectors
• The strong circular law: A combinatorial view
• Optimal and algorithmic norm regularization of random matrices
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

This page was built for publication: Norms of random matrices: local and global problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1684656)