Name
Abstract | ||
|---|---|---|
We consider the estimation of a n-dimensional vector x from the knowledge of noisy and possibility non-linear element-wise measurements of xx
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup>
, a very generic problem that contains, e.g. stochastic 2-block model, submatrix localization or the spike perturbation of random matrices. Using an interpolation method proposed by Guerra [1] and later refined by Korada and Macris [2], we prove that the Bethe mutual information (related to the Bethe free energy and conjectured to be exact by Lesieur et al. [3] on the basis of the non-rigorous cavity method) always yields an upper bound to the exact mutual information. A lower bound is also provided using a similar technique. For concreteness, we illustrate our findings on the sparse PCA problem, and observe that (a) our bounds match for a large region of parameters and (b) that there exists a phase transition in a region where the spectrum remains uninformative. While we present only the case of rank-one symmetric matrix estimation, our proof technique is readily extendable to low-rank symmetric matrix or low-rank symmetric tensor estimation. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/ITW.2016.7606798 | 2016 IEEE Information Theory Workshop (ITW) |
Keywords | DocType | Volume |
mutual information,random matrices,sparse PCA problem,rank-one symmetric matrix estimation,low-rank symmetric tensor estimation,interpolation method | Conference | abs/1603.08447 |
ISBN | Citations | PageRank |
978-1-5090-1091-2 | 18 | 0.94 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Florent Krzakala | 1 | 977 | 67.30 |
| Jiaming Xu | 2 | 238 | 16.14 |
| Lenka Zdeborová | 3 | 1190 | 78.62 |