Regularization conjecture for random matrix operator norms

About 8 years old · traced to

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

E⁡Aij2=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

∥row⁡i(A)∥m≥CE⁡∥row⁡i(A)∥mor∥col⁡i(A)∥m≥CE⁡∥col⁡i(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,C′C,C' such that, with probability 1−o(1)1-o(1), the operator norm of the resulting matrix satisfies

∥A~∥≤C′n.\|\tilde{A}\|\leq C'\sqrt{n}.

The conjecture seeks to remove the extra ln⁡ln⁡n\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.