Publications by Emmanuel Abbé

Related publications (43)

AN l(p) THEORY OF PCA AND SPECTRAL CLUSTERING

Principal Component Analysis (PCA) is a powerful tool in statistics and machine learning. While existing study of PCA focuses on the recovery of principal components and their associated eigenvalues, there are few precise characterizations of individual pr ...

Institute of Mathematical Statistics2022

A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels

Emmanuel Abbé, Colin Peter Sandon

In 1948, Shannon used a probabilistic argument to show that there exist codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve chann ...

Ieee Computer Soc2023

Chaining Mutual Information and Tightening Generalization Bounds

Emmanuel Abbé

Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the h ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

Polar Codes for the m-User Multiple Access Channel

Emre Telatar, Emmanuel Abbé

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into su ...

Institute of Electrical and Electronics Engineers2012

Reed-Muller Codes

Emmanuel Abbé

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under inv ...

Emerald2023

Reed-Muller Codes: Theory and Algorithms

Emmanuel Abbé, Min Ye

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under inv ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Graph Powering and Spectral Robustness

Emmanuel Abbé

Spectral algorithms, such as principal component analysis and spectral clustering, rely on the extremal eigenpairs of a matrix A. However, these may be uninformative without preprocessing A with a proper transformation. The reason is that the spectrum of A ...

SIAM PUBLICATIONS2020

Almost-Reed-Muller Codes Achieve Constant Rates for Random Errors

Emmanuel Abbé, Jan Hazla, Ido Nachum

This paper considers "delta-almost Reed-Muller codes", i.e., linear codes spanned by evaluations of all but a delta fraction of monomials of degree at most d. It is shown that for any delta > 0 and any epsilon > 0, there exists a family of delta-almost Ree ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Anatomy-Informed Multimodal Learning for Myocardial Infarction Prediction

Pascal Frossard, Emmanuel Abbé, Ntorina Thanou, Ortal Yona Senouf, Ivan-Daniel Sievering

Goal: In patients with coronary artery disease, the prediction of future cardiac events such as myocardial infarction (MI) remains a major challenge. In this work, we propose a novel anatomy-informed multimodal deep learning framework to predict future MI ...

2024

Polynomial-time universality and limitations of deep learning

Emmanuel Abbé

The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly-time ...

WILEY2023

A New Entropy Power Inequality for Integer-Valued Random Variables

Emmanuel Abbé, Saeid Haghighatshoar

The entropy power inequality (EPI) yields lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for spe ...

Institute of Electrical and Electronics Engineers2014

Polar Codes for the m-User MAC

Emre Telatar, Emmanuel Abbé

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arıkan’s polarization technique applied individually to each user transforms independent uses of a m-user binary input MAC into suc ...

Institute of Electrical and Electronics Engineers2012

Gender Bias in AI's Perception of Cardiovascular Risk

Emmanuel Abbé

The study investigated gender bias in GPT-4's assessment of coronary artery disease risk by presenting identical clinical vignettes of men and women with and without psychiatric comorbidities. Results suggest that psychiatric conditions may influence GPT-4 ...

2024

Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold

Emmanuel Abbé

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succe ...

INST MATHEMATICAL STATISTICS-IMS2023

Polar Codes For Broadcast Channels

Michael Christoph Gastpar, Emmanuel Abbé, Naveen Goela

Building on polar code constructions proposed by the authors for deterministic broadcast channels, two theorems are introduced in the present paper for noisy two-user broadcast channels. The theorems establish polar code constructions for two important ...

2013

Polarization of the Renyi Information Dimension With Applications to Compressed Sensing

Emmanuel Abbé, Saeid Haghighatshoar

In this paper, we show that the Hadamard matrix acts as an extractor over the reals of the Renyi Information Dimension (RID), in an analogous way to how it acts as an extractor of the discrete entropy over finite fields. More precisely, we prove that the R ...

Ieee-Inst Electrical Electronics Engineers Inc2017

Adaptive sensing using deterministic partial Hadamard matrices

Emre Telatar, Emmanuel Abbé, Saeid Haghighatshoar

This paper investigates the construction of determin- istic measurement matrices preserving the entropy of a random vector with a given probability distribution. In particular, it is shown that for a random vector with i.i.d. discrete components, this is a ...

Ieee2012

Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Networks

Emmanuel Abbé

We derive generalization and excess risk bounds for neural networks using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural networks and b ...

Microtome Publishing2020

Predicting future myocardial infarction from angiographies with deep learning

Omar Raita, Pascal Frossard, Emmanuel Abbé, Ntorina Thanou, Ortal Yona Senouf, Thabodhan Mahendiran

In patients with stable Coronary Artery Disease (CAD), the identification of lesions which will be responsible of a myocardial infarction (MI) during follow-up remains a daily challenge. In this work, we propose to predict culprit stenosis by applying a de ...

2021

Binary Perceptron: Efficient Algorithms Can Find Solutions in a RareWell-Connected Cluster

Emmanuel Abbé

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in fin ...

ASSOC COMPUTING MACHINERY2022