Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel

Abstract : This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of it's elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but standard assumptions motivated by statistical physics, we characterize the minimum mean squared error (MMSE) achievable information theoretically and with the AMP algorithm. Unlike in related problems of linear estimation, in the present setting the MMSE depends on the output channel only trough a single parameter -- its the Fisher information. We illustrate this striking finding by analysis of submatrix localization, and of detection of communities hidden in a dense stochastic block model. For this example we locate the computational and statistical boundaries that are not equal for rank larger than four.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal-cea.archives-ouvertes.fr/cea-01222294
Contributor : Emmanuelle de Laborderie <>
Submitted on : Thursday, October 29, 2015 - 4:04:30 PM
Last modification on : Saturday, October 17, 2020 - 3:12:41 AM

Links full text

Identifiers

  • HAL Id : cea-01222294, version 1
  • ARXIV : 1507.03857

Citation

Thibault Lesieur, Florent Krzakala, Lenka Zdeborová. MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel. 2015. ⟨cea-01222294⟩

Share

Metrics

Record views

146