The conjectured optimal efficient mean square error for symmetric low-rank estimation

Let XX have prior distribution P0P_0, and consider the symmetric rank-one matrix estimation model with signal-to-noise parameter λ\lambda. For η>0\eta>0, define

qη0=η,qηt+1=EP0[X2]mmse(λqηt),q^0_\eta=\eta,\qquad q^{t+1}_\eta=\mathbb{E}_{P_0}[X^2]-\operatorname{mmse}(\lambda q^t_\eta),

and set

q~=limη0limtqηt.\widetilde q=\lim_{\eta\to0}\lim_{t\to\infty}q^t_\eta.

Here mmse\operatorname{mmse} denotes the scalar minimum mean square error. The efficient-estimation conjecture. For the model, the best mean square error achievable by an efficient algorithm is

EP0[X2]2q~2.\mathbb{E}_{P_0}[X^2]^2-\widetilde q^2.

This conjecture proposes that the state-evolution limit determines the optimal performance of efficient algorithms, addressing both whether the dummy-estimator error can be beaten efficiently and whether the information-theoretic minimum error can be attained; the source does not give a resolution.

Sources & referencesView supporting material

Primary source

Marc Lelarge and Léo Miolane, “Fundamental limits of symmetric low-rank matrix estimation”, arXiv:1611.03888 (2017).

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.