Nicolas Macris

Dr. Nicolas Macris


Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 March 2019 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Open access
PDF file
JBJean Barbier
Jean Barbier
FKFlorent Krzakala
Florent Krzakala
NMNicolas Macris
Nicolas Macris
LMLéo Miolane
Léo Miolane
LZLenka Zdeborová
Lenka Zdeborová
Generalized linear models (GLMs) are used in high-dimensional machine learning, statistics, communications, and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes, or benchmark models in neural networks. We evaluate the mutual information (or “free entropy”) from which we deduce the Bayes-optimal estimation and generalization errors. Our analysis applies to the high-dimensional limit where both the number of samples and the dimension are large and their ratio is fixed. Nonrigorous predictions for the optimal errors existed for special cases of GLMs, e.g., for the perceptron, in the field of statistical physics based on the so-called replica method. Our present paper rigorously establishes those decades-old conjectures and brings forward their algorithmic interpretation in terms of performance of the generalized approximate message-passing algorithm. Furthermore, we tightly characterize, for many learning problems, regions of parameters for which this algorithm achieves the optimal performance and locate the associated sharp phase transitions separating learnable and nonlearnable regions. We believe that this random version of GLMs can serve as a challenging benchmark for multipurpose algorithms.

23 April 2019 in Advanced Quantum Technologies
Verified
Journal Article
Open access
PDF file
DCDiogo Cruz
Diogo Cruz
RFRomain Fournier
Romain Fournier
FGFabien Gremion
Fabien Gremion
AJAlix Jeannerot
Alix Jeannerot
KKKenichi Komagata
Kenichi Komagata
CJClément Javerzac‐Galy
Clément Javerzac‐Galy
Efficient deterministic algorithms are proposed with logarithmic step complexities for the generation of entangled and states useful for quantum networks, and an implementation on the IBM quantum computer up to is demonstrated. Improved quality is then investigated using full quantum tomography for low‐ N GHZ and W states. This is completed by parity oscillations and histogram distance for large‐ N GHZ and W states, respectively. Robust states are built with about twice the number of quantum bits which were previously achieved.

28 April 2020 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
JBJean Barbier
Jean Barbier
NMNicolas Macris
Nicolas Macris
MDMohamad Dia
Mohamad Dia
FKFlorent Krzakala
Florent Krzakala
We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections. A few examples where this problem is relevant are compressed sensing, sparse superposition codes, and code division multiple access. There has been a number of works considering the mutual information for this problem using the replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-Toninelli type interpolation, that the replica formula yields an upper bound to the exact mutual information. Secondly, for many relevant practical cases, we present a converse lower bound via a method that uses spatial coupling, state evolution analysis and the IMMSE theorem. This yields a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals. In addition, we prove that the low complexity approximate messagepassing algorithm is optimal outside of the so-called hard phase, in the sense that it asymptotically reaches the minimal-meansquare error. In this work spatial coupling is used primarily as a proof technique. However our results also prove two important features of spatially coupled noisy linear random Gaussian estimation. First there is no algorithmically hard phase. This means that for such systems approximate message-passing always reaches the minimal-mean-square error. Secondly, in the limit of infinitely long coupled chain, the mutual information associated to spatially coupled systems is the same as the one of uncoupled linear random Gaussian estimation.

11 July 2009 in Journal of Statistical Physics
Verified
Journal Article
Closed access
PDF file
SKSatish Babu Korada
Satish Babu Korada
NMNicolas Macris
Nicolas Macris

30 August 2022 in Physical Review E
Verified
Journal Article
Closed access
PDF file
JBJean Barbier
Jean Barbier
NMNicolas Macris
Nicolas Macris
We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, in the challenging regime where the matrices to infer have a rank growing linearly with the system size. This is in contrast with most existing literature concerned with the low-rank (i.e., constant-rank) regime. We first consider a class of rotationally invariant matrix denoising problems whose mutual information and minimum mean-square error are computable using techniques from random matrix theory. Next, we analyze the more challenging models of dictionary learning. To do so we introduce a combination of the replica method from statistical mechanics together with random matrix theory, coined spectral replica method. This allows us to derive variational formulas for the mutual information between hidden representations and the noisy data of the dictionary learning problem, as well as for the overlaps quantifying the optimal reconstruction error. The proposed method reduces the number of degrees of freedom from Θ(N2) matrix entries to Θ(N) eigenvalues (or singular values), and yields Coulomb gas representations of the mutual information which are reminiscent of matrix models in physics. The main ingredients are a combination of large deviation results for random matrices together with a replica symmetric decoupling ansatz at the level of the probability distributions of eigenvalues (or singular values) of certain overlap matrices and the use of Harish-Chandra-Itzykson-Zuber spherical integrals.

28 May 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
JBJean Barbier
Jean Barbier
MDMohamad Dia
Mohamad Dia
NMNicolas Macris
Nicolas Macris
Sparse superposition codes, or sparse regression codes, constitute a new class of codes which was first introduced for communication over the additive white Gaussian noise (AWGN) channel. It has been shown that such codes are capacity-achieving over the AWGN channel under optimal maximum-likelihood decoding as well as under various efficient iterative decoding schemes equipped with power allocation or spatially coupled constructions. Here, we generalize the analysis of these codes to a much broader setting that includes all memoryless channels. We show, for a large class of memoryless channels, that spatial coupling allows an efficient decoder, based on the generalized approximate message-passing (GAMP) algorithm, to reach the potential (or Bayes optimal) threshold of the underlying (or uncoupled) code ensemble. Moreover, we argue that spatially coupled sparse superposition codes universally achieve capacity under GAMP decoding by showing, through analytical computations, that the error floor vanishes and the potential threshold tends to capacity as one of the code parameter goes to infinity. Furthermore, we provide a closed form formula for the algorithmic threshold of the underlying code ensemble in terms of a Fisher information. Relating an algorithmic threshold to a Fisher information has theoretical as well as practical importance. Our proof relies on the state evolution analysis and uses the potential method developed in the theory of low-density parity-check (LDPC) codes and compressed sensing.