Constructive Regularization of the Random Matrix Norm

Elizaveta Rebrova ()
Additional contact information
Elizaveta Rebrova: UCLA

Journal of Theoretical Probability, 2020, vol. 33, issue 3, 1768-1790

Abstract: Abstract We study the structure of $$n \times n$$ n × n random matrices with centered i.i.d. entries having only two finite moments. In the recent joint work with R. Vershynin, we have shown that the operator norm of such matrix A can be reduced to the optimal order $$O(\sqrt{n})$$ O ( n ) with high probability by zeroing out a small submatrix of A, but did not describe the structure of this “bad” submatrix nor provide a constructive way to find it. In the current paper, we give a very simple description of a small “bad” subset of entries. We show that it is enough to zero out a small fraction of the rows and columns of A with largest $$L_2$$ L 2 norms to bring the operator norm of A to the almost optimal order $$O(\sqrt{n \log \log n})$$ O ( n log log n ) , under additional assumption that the matrix entries are symmetrically distributed. As a corollary, we also obtain a constructive procedure to find a small submatrix of A that one can zero out to achieve the same norm regularization. The main component of the proof is the development of techniques extending constructive regularization approaches known for the Bernoulli matrices (from the works of Feige and Ofek, and Le, Levina and Vershynin) to the considerably broader class of heavy-tailed random matrices.

Keywords: Random matrices; Operator norms; Heavy tails; 60B20; 15B52 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-019-00929-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:33:y:2020:i:3:d:10.1007_s10959-019-00929-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-019-00929-6

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().