2018/10/06 by Montanari, Andrea, Ruan, Feng, Yan, Jun
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Methodology (stat.ME) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1810.02954
We consider the problem of estimating an unknown matrix \boldsymbolX∈ \mathbb Rm× n, from observations \boldsymbolY = \boldsymbolX+\boldsymbolW where \boldsymbolW is a noise matrix with independent and identically distributed entries, as to minimize estimation error measured in operator norm. Assuming that the underlying signal \boldsymbolX is low-rank and incoherent with respect to the canonical basis, we prove that minimax risk is equivalent to (√(m)\vee√(n))/√(IW) in the high-dimensional limit m,n→∞, where IW is the Fisher information of the noise. Crucially, we develop an efficient procedure that achieves this risk, adaptively over the noise distribution (under certain regularity assumptions). Letting \boldsymbolX = \boldsymbolU\boldsymbolΣ\boldsymbolV\sf T --where \boldsymbolU∈ \mathbb Rm× r, \boldsymbolV∈\mathbb Rn× r are orthogonal, and r is kept fixed as m,n→∞-- we use our method to estimate \boldsymbolU, \boldsymbolV. Standard spectral methods provide non-trivial estimates of the factors \boldsymbolU,\boldsymbolV (weak recovery) only if the singular values of \boldsymbolX are larger than (mn)1/4\rm Var(W11)1/2. We prove that the new approach achieves weak recovery down to the the information-theoretically optimal threshold (mn)1/4IW1/2.