Norms of random matrices: local and global problems

DOI10.1016/J.AIM.2017.11.001zbMATH Open1380.60016arXiv1608.06953OpenAlexW2963081812MaRDI QIDQ1684656FDOQ1684656

Authors: Elizaveta Rebrova, Roman Vershynin 

Publication date: 12 December 2017

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

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.

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

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

zbMATH Keywords

heavy tailsrandom matricesoperator normBai-Yin law

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20)

Cites Work

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

Cited In (7)

• 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
• Norms on complex matrices induced by random vectors
• Sparse random tensors: concentration, regularization and applications
• Outliers in spectrum of sparse Wigner matrices
• Constructive regularization of the random matrix norm

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)