ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let d>1d>1, n>2n>2, m≥d+1m\geq d+1, A∈Rd×mA\in\mathbb{R}^{d\times m} represent mm random points in Rd\mathbb{R}^d (i.i.d. uniform random coordinates in [0,1]d[0,1]^d), and let Oii=1n\\{O_i\\}_{i=1}^n be any sequence of orthogonal transformations. Let Ai=OiA+σηi∈Rd×mA_i=O_iA+\sigma\eta_i\in\mathbb{R}^{d\times m}, where ηi\eta_i is a matrix with i.i.d. standard Gaussian entries. Rank recovery conjecture. There exists σ∗>0\sigma_{\ast}>0 such that, for σ<σ∗\sigma<\sigma_{\ast}, with high probability, the solution of the SDP relaxation has rank dd, and hence matches the quasi-maximum-likelihood estimator. Here the SDP relaxation is the formulation obtained by dropping the rank constraint from the quasi-maximum-likelihood formulation. The conjecture concerns the rank-recovery phenomenon observed numerically in generalized Procrustes problems; establishing it would provide a theoretical explanation for why the semidefinite relaxation is tight below a noise threshold.

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.