ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.