Regularization conjecture for random matrix operator norms

From papers

Let AA be an n×nn \times n random matrix with i.i.d. mean-zero entries satisfying

EAij2=1.\operatorname{\mathbb{E}} A_{ij}^2=1.

For a suitable LmL_m-norm, let A~\tilde{A} be obtained from AA by zeroing out every row and column satisfying

rowi(A)mCErowi(A)morcoli(A)mCEcoli(A)m.\|\operatorname{row}_i(A)\|_m \geq C\operatorname{\mathbb{E}}\|\operatorname{row}_i(A)\|_m \quad\text{or}\quad \|\operatorname{col}_i(A)\|_m \geq C\operatorname{\mathbb{E}}\|\operatorname{col}_i(A)\|_m.

Here mm is to be specified, with m=2m=2 as an example. Regularization conjecture. There are constants C,CC,C' such that, with probability 1o(1)1-o(1), the operator norm of the resulting matrix satisfies

A~Cn.\|\tilde{A}\|\leq C'\sqrt{n}.

The conjecture seeks to remove the extra lnlnn\sqrt{\ln\ln n} factor from the optimal n\sqrt{n} order in the authors' regularization result, and also to avoid the assumption that the entry distribution is symmetric. The required choice of LmL_m-norm remains unspecified; the statement is presented as a potential improvement rather than an established theorem.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Elizaveta Rebrova, “Constructive regularization of the random matrix norm”, arXiv:1809.03926 (2018).

Solutions 0

No solutions have been posted yet.