Timezone: »
Poster
Matrix Completion from Fewer Entries: Spectral Detectability and Rank Estimation
Alaa Saade · Florent Krzakala · Lenka Zdeborová
The completion of low rank matrices from few entries is a task with many practical applications. We consider here 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 propose 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 analyze the performance in a random matrix setting using results from the statistical mechanics of the Hopfield neural network, and show in particular that MaCBetH efficiently detects the rank $r$ of a large $n\times m$ matrix from $C(r)r\sqrt{nm}$ entries, where $C(r)$ is a constant close to $1$. We also evaluate the corresponding root-mean-square error empirically and show that MaCBetH compares favorably to other existing approaches.
Author Information
Alaa Saade (ENS)
Florent Krzakala (Ecole Normale Superieure Paris)
Lenka Zdeborová (CEA)
More from the Same Authors
-
2021 Spotlight: Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions »
Bruno Loureiro · Gabriele Sicuro · Cedric Gerbelot · Alessandro Pacco · Florent Krzakala · Lenka Zdeborová -
2022 Workshop: Machine Learning and the Physical Sciences »
Atilim Gunes Baydin · Adji Bousso Dieng · Emine Kucukbenli · Gilles Louppe · Siddharth Mishra-Sharma · Benjamin Nachman · Brian Nord · Savannah Thais · Anima Anandkumar · Kyle Cranmer · Lenka Zdeborová · Rianne van den Berg -
2022 Poster: Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks »
Rodrigo Veiga · Ludovic Stephan · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová -
2022 Poster: Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap »
Luca Pesce · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová -
2022 Poster: Multi-layer State Evolution Under Random Convolutional Design »
Max Daniels · Cedric Gerbelot · Florent Krzakala · Lenka Zdeborová -
2021 Workshop: Machine Learning and the Physical Sciences »
Anima Anandkumar · Kyle Cranmer · Mr. Prabhat · Lenka Zdeborová · Atilim Gunes Baydin · Juan Carrasquilla · Emine Kucukbenli · Gilles Louppe · Benjamin Nachman · Brian Nord · Savannah Thais -
2021 Poster: Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions »
Bruno Loureiro · Gabriele Sicuro · Cedric Gerbelot · Alessandro Pacco · Florent Krzakala · Lenka Zdeborová -
2021 Poster: Learning curves of generic features maps for realistic datasets with a teacher-student model »
Bruno Loureiro · Cedric Gerbelot · Hugo Cui · Sebastian Goldt · Florent Krzakala · Marc Mezard · Lenka Zdeborová -
2021 Poster: Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime »
Hugo Cui · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová -
2020 : Orals 2.2: Hardware Beyond Backpropagation: a Photonic Co-Processor for Direct Feedback Alignmen »
Julien Launay · Iacopo Poli · Laurent Daudet · Florent Krzakala -
2020 : Opening Remarks »
Reinhard Heckel · Paul Hand · Soheil Feizi · Lenka Zdeborová · Richard Baraniuk -
2020 Workshop: Workshop on Deep Learning and Inverse Problems »
Reinhard Heckel · Paul Hand · Richard Baraniuk · Lenka Zdeborová · Soheil Feizi -
2020 Workshop: Machine Learning and the Physical Sciences »
Anima Anandkumar · Kyle Cranmer · Shirley Ho · Mr. Prabhat · Lenka Zdeborová · Atilim Gunes Baydin · Juan Carrasquilla · Adji Bousso Dieng · Karthik Kashinath · Gilles Louppe · Brian Nord · Michela Paganini · Savannah Thais -
2020 Poster: Direct Feedback Alignment Scales to Modern Deep Learning Tasks and Architectures »
Julien Launay · Iacopo Poli · François Boniface · Florent Krzakala -
2020 Poster: Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization »
Benjamin Aubin · Florent Krzakala · Yue Lu · Lenka Zdeborová -
2020 Poster: Reservoir Computing meets Recurrent Kernels and Structured Transforms »
Jonathan Dong · Ruben Ohana · Mushegh Rafayelyan · Florent Krzakala -
2020 Oral: Reservoir Computing meets Recurrent Kernels and Structured Transforms »
Jonathan Dong · Ruben Ohana · Mushegh Rafayelyan · Florent Krzakala -
2020 Poster: Phase retrieval in high dimensions: Statistical and computational phase transitions »
Antoine Maillard · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová -
2020 Poster: Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification »
Francesca Mignacco · Florent Krzakala · Pierfrancesco Urbani · Lenka Zdeborová -
2020 Poster: Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval »
Stefano Sarao Mannelli · Giulio Biroli · Chiara Cammarota · Florent Krzakala · Pierfrancesco Urbani · Lenka Zdeborová -
2019 : Lenka Zdeborova »
Lenka Zdeborová -
2019 : Lunch Break and Posters »
Xingyou Song · Elad Hoffer · Wei-Cheng Chang · Jeremy Cohen · Jyoti Islam · Yaniv Blumenfeld · Andreas Madsen · Jonathan Frankle · Sebastian Goldt · Satrajit Chatterjee · Abhishek Panigrahi · Alex Renda · Brian Bartoldson · Israel Birhane · Aristide Baratin · Niladri Chatterji · Roman Novak · Jessica Forde · YiDing Jiang · Yilun Du · Linara Adilova · Michael Kamp · Berry Weinstein · Itay Hubara · Tal Ben-Nun · Torsten Hoefler · Daniel Soudry · Hsiang-Fu Yu · Kai Zhong · Yiming Yang · Inderjit Dhillon · Jaime Carbonell · Yanqing Zhang · Dar Gilboa · Johannes Brandstetter · Alexander R Johansen · Gintare Karolina Dziugaite · Raghav Somani · Ari Morcos · Freddie Kalaitzis · Hanie Sedghi · Lechao Xiao · John Zech · Muqiao Yang · Simran Kaur · Qianli Ma · Yao-Hung Hubert Tsai · Ruslan Salakhutdinov · Sho Yaida · Zachary Lipton · Daniel Roy · Michael Carbin · Florent Krzakala · Lenka Zdeborová · Guy Gur-Ari · Ethan Dyer · Dilip Krishnan · Hossein Mobahi · Samy Bengio · Behnam Neyshabur · Praneeth Netrapalli · Kris Sankaran · Julien Cornebise · Yoshua Bengio · Vincent Michalski · Samira Ebrahimi Kahou · Md Rifat Arefin · Jiri Hron · Jaehoon Lee · Jascha Sohl-Dickstein · Samuel Schoenholz · David Schwab · Dongyu Li · Sang Keun Choe · Henning Petzka · Ashish Verma · Zhichao Lin · Cristian Sminchisescu -
2019 : Surya Ganguli, Yasaman Bahri, Florent Krzakala moderated by Lenka Zdeborova »
Florent Krzakala · Yasaman Bahri · Surya Ganguli · Lenka Zdeborová · Adji Bousso Dieng · Joan Bruna -
2019 : Poster Session »
Jonathan Scarlett · Piotr Indyk · Ali Vakilian · Adrian Weller · Partha P Mitra · Benjamin Aubin · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová · Kristina Monakhova · Joshua Yurtsever · Laura Waller · Hendrik Sommerhoff · Michael Moeller · Rushil Anirudh · Shuang Qiu · Xiaohan Wei · Zhuoran Yang · Jayaraman Thiagarajan · Salman Asif · Michael Gillhofer · Johannes Brandstetter · Sepp Hochreiter · Felix Petersen · Dhruv Patel · Assad Oberai · Akshay Kamath · Sushrut Karmalkar · Eric Price · Ali Ahmed · Zahra Kadkhodaie · Sreyas Mohan · Eero Simoncelli · Carlos Fernandez-Granda · Oscar Leong · Wesam Sakla · Rebecca Willett · Stephan Hoyer · Jascha Sohl-Dickstein · Sam Greydanus · Gauri Jagatap · Chinmay Hegde · Michael Kellman · Jonathan Tamir · Nouamane Laanait · Ousmane Dia · Mirco Ravanelli · Jonathan Binas · Negar Rostamzadeh · Shirin Jalali · Tiantian Fang · Alex Schwing · Sébastien Lachapelle · Philippe Brouillard · Tristan Deleu · Simon Lacoste-Julien · Stella Yu · Arya Mazumdar · Ankit Singh Rawat · Yue Zhao · Jianshu Chen · Xiaoyang Li · Hubert Ramsauer · Gabrio Rizzuti · Nikolaos Mitsakos · Dingzhou Cao · Thomas Strohmer · Yang Li · Pei Peng · Gregory Ongie -
2019 : The spiked matrix model with generative priors »
Lenka Zdeborová -
2019 Poster: The spiked matrix model with generative priors »
Benjamin Aubin · Bruno Loureiro · Antoine Maillard · Florent Krzakala · Lenka Zdeborová -
2016 Poster: Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula »
jean barbier · Mohamad Dia · Nicolas Macris · Florent Krzakala · Thibault Lesieur · Lenka Zdeborová -
2015 Poster: Training Restricted Boltzmann Machine via the Thouless-Anderson-Palmer free energy »
Marylou Gabrie · Eric W Tramel · Florent Krzakala -
2014 Poster: Spectral Clustering of graphs with the Bethe Hessian »
Alaa Saade · Florent Krzakala · Lenka Zdeborová