July 2nd
14:30 , R2014 Digiteo Shannon (660) (see location):Alaa Saade
Title: MaCBetH : Matrix Completion with the Bethe Hessian
Abstract :
The completion of low rank matrices from few entries is a task with many practical applications. We will consider two aspects of this problem: detectability, i.e. the ability to estimate the rank r reliably from the fewest possible random entries, and performance in achieving small reconstruction error. We will introduce a spectral algorithm for these two tasks called MaCBetH (for Matrix Completion with the Bethe Hessian). The rank is estimated as the number of negative eigenvalues of the Bethe Hessian matrix, and the corresponding eigenvectors are used as initial condition for the minimization of the discrepancy between the estimated matrix and the revealed entries.We will analyze the performance in a random matrix setting using results from the statistical mechanics of the Hopfield neural network, and identify a phase transition between a regime in which MaCBetH is able to infer the correct rank and a phase where it is unable to do so. We will also evaluate the corresponding root-mean-square error empirically and show that MaCBetH compares favorably to other existing approaches. Finally, we will discuss the applicability of some of the core ideas behind this algorithm to other inference problems, in particular community detection.
Contact: cyril.furtlehner à inria.fr