Constructive Regularization of the Random Matrix Norm

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We study the structure of 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(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 L2 norms to bring the operator norm of A to the almost optimal order O(nloglogn), 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.

Original languageEnglish (US)
Pages (from-to)1768-1790
Number of pages23
JournalJournal of Theoretical Probability
Volume33
Issue number3
DOIs
StatePublished - Sep 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

Keywords

  • Heavy tails
  • Operator norms
  • Random matrices

Fingerprint

Dive into the research topics of 'Constructive Regularization of the Random Matrix Norm'. Together they form a unique fingerprint.

Cite this