---
_id: '12480'
abstract:
- lang: eng
  text: 'We consider the problem of estimating a signal from measurements obtained
    via a generalized linear model. We focus on estimators based on approximate message
    passing (AMP), a family of iterative algorithms with many appealing features:
    the performance of AMP in the high-dimensional limit can be succinctly characterized
    under suitable model assumptions; AMP can also be tailored to the empirical distribution
    of the signal entries, and for a wide class of estimation problems, AMP is conjectured
    to be optimal among all polynomial-time algorithms. However, a major issue of
    AMP is that in many models (such as phase retrieval), it requires an initialization
    correlated with the ground-truth signal and independent from the measurement matrix.
    Assuming that such an initialization is available is typically not realistic.
    In this paper, we solve this problem by proposing an AMP algorithm initialized
    with a spectral estimator. With such an initialization, the standard AMP analysis
    fails since the spectral estimator depends in a complicated way on the design
    matrix. Our main contribution is a rigorous characterization of the performance
    of AMP with spectral initialization in the high-dimensional limit. The key technical
    idea is to define and analyze a two-phase artificial AMP algorithm that first
    produces the spectral estimator, and then closely approximates the iterates of
    the true AMP. We also provide numerical results that demonstrate the validity
    of the proposed approach.'
acknowledgement: "The authors would like to thank Andrea Montanari for helpful discussions.\r\nM
  Mondelli was partially supported by the 2019 Lopez-Loreta Prize. R Venkataramanan
  was partially supported by the Alan Turing Institute under the EPSRC Grant\r\nEP/N510129/1."
article_number: '114003'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Marco
  full_name: Mondelli, Marco
  id: 27EB676C-8706-11E9-9510-7717E6697425
  last_name: Mondelli
  orcid: 0000-0002-3242-7020
- first_name: Ramji
  full_name: Venkataramanan, Ramji
  last_name: Venkataramanan
citation:
  ama: 'Mondelli M, Venkataramanan R. Approximate message passing with spectral initialization
    for generalized linear models. <i>Journal of Statistical Mechanics: Theory and
    Experiment</i>. 2022;2022(11). doi:<a href="https://doi.org/10.1088/1742-5468/ac9828">10.1088/1742-5468/ac9828</a>'
  apa: 'Mondelli, M., &#38; Venkataramanan, R. (2022). Approximate message passing
    with spectral initialization for generalized linear models. <i>Journal of Statistical
    Mechanics: Theory and Experiment</i>. IOP Publishing. <a href="https://doi.org/10.1088/1742-5468/ac9828">https://doi.org/10.1088/1742-5468/ac9828</a>'
  chicago: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing
    with Spectral Initialization for Generalized Linear Models.” <i>Journal of Statistical
    Mechanics: Theory and Experiment</i>. IOP Publishing, 2022. <a href="https://doi.org/10.1088/1742-5468/ac9828">https://doi.org/10.1088/1742-5468/ac9828</a>.'
  ieee: 'M. Mondelli and R. Venkataramanan, “Approximate message passing with spectral
    initialization for generalized linear models,” <i>Journal of Statistical Mechanics:
    Theory and Experiment</i>, vol. 2022, no. 11. IOP Publishing, 2022.'
  ista: 'Mondelli M, Venkataramanan R. 2022. Approximate message passing with spectral
    initialization for generalized linear models. Journal of Statistical Mechanics:
    Theory and Experiment. 2022(11), 114003.'
  mla: 'Mondelli, Marco, and Ramji Venkataramanan. “Approximate Message Passing with
    Spectral Initialization for Generalized Linear Models.” <i>Journal of Statistical
    Mechanics: Theory and Experiment</i>, vol. 2022, no. 11, 114003, IOP Publishing,
    2022, doi:<a href="https://doi.org/10.1088/1742-5468/ac9828">10.1088/1742-5468/ac9828</a>.'
  short: 'M. Mondelli, R. Venkataramanan, Journal of Statistical Mechanics: Theory
    and Experiment 2022 (2022).'
date_created: 2023-02-02T08:31:57Z
date_published: 2022-11-24T00:00:00Z
date_updated: 2024-03-07T10:36:52Z
day: '24'
ddc:
- '510'
- '530'
department:
- _id: MaMo
doi: 10.1088/1742-5468/ac9828
external_id:
  isi:
  - '000889589900001'
file:
- access_level: open_access
  checksum: 01411ffa76d3e380a0446baeb89b1ef7
  content_type: application/pdf
  creator: dernst
  date_created: 2023-02-02T08:35:52Z
  date_updated: 2023-02-02T08:35:52Z
  file_id: '12481'
  file_name: 2022_JourStatisticalMechanics_Mondelli.pdf
  file_size: 1729997
  relation: main_file
  success: 1
file_date_updated: 2023-02-02T08:35:52Z
has_accepted_license: '1'
intvolume: '      2022'
isi: 1
issue: '11'
keyword:
- Statistics
- Probability and Uncertainty
- Statistics and Probability
- Statistical and Nonlinear Physics
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 059876FA-7A3F-11EA-A408-12923DDC885E
  name: Prix Lopez-Loretta 2019 - Marco Mondelli
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
  issn:
  - 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
  record:
  - id: '10598'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Approximate message passing with spectral initialization for generalized linear
  models
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022
year: '2022'
...
---
_id: '9158'
abstract:
- lang: eng
  text: While several tools have been developed to study the ground state of many-body
    quantum spin systems, the limitations of existing techniques call for the exploration
    of new approaches. In this manuscript we develop an alternative analytical and
    numerical framework for many-body quantum spin ground states, based on the disentanglement
    formalism. In this approach, observables are exactly expressed as Gaussian-weighted
    functional integrals over scalar fields. We identify the leading contribution
    to these integrals, given by the saddle point of a suitable effective action.
    Analytically, we develop a field-theoretical expansion of the functional integrals,
    performed by means of appropriate Feynman rules. The expansion can be truncated
    to a desired order to obtain analytical approximations to observables. Numerically,
    we show that the disentanglement approach can be used to compute ground state
    expectation values from classical stochastic processes. While the associated fluctuations
    grow exponentially with imaginary time and the system size, this growth can be
    mitigated by means of an importance sampling scheme based on knowledge of the
    saddle point configuration. We illustrate the advantages and limitations of our
    methods by considering the quantum Ising model in 1, 2 and 3 spatial dimensions.
    Our analytical and numerical approaches are applicable to a broad class of systems,
    bridging concepts from quantum lattice models, continuum field theory, and classical
    stochastic processes.
acknowledgement: "S D N would like to thank M J Bhaseen, J Chalker, B Doyon, V Gritsev,
  A Lamacraft,\r\nA Michailidis and M Serbyn for helpful feedback and stimulating
  conversations. S D N\r\nacknowledges funding from the Institute of Science and Technology
  (IST) Austria, and\r\nfrom the European Union’s Horizon 2020 research and innovation
  program under the\r\nMarie Sk\blodowska-Curie Grant Agreement No. 754411. S D N
  also acknowledges funding\r\nfrom the EPSRC Center for Doctoral Training in Cross-Disciplinary
  Approaches to Non-\r\nEquilibrium Systems (CANES) under Grant EP/L015854/1. S D
  N is grateful to IST\r\nAustria for providing open access funding."
article_number: '013101'
article_processing_charge: No
article_type: original
author:
- first_name: Stefano
  full_name: De Nicola, Stefano
  id: 42832B76-F248-11E8-B48F-1D18A9856A87
  last_name: De Nicola
  orcid: 0000-0002-4842-6671
citation:
  ama: 'De Nicola S. Disentanglement approach to quantum spin ground states: Field
    theory and stochastic simulation. <i>Journal of Statistical Mechanics: Theory
    and Experiment</i>. 2021;2021(1). doi:<a href="https://doi.org/10.1088/1742-5468/abc7c7">10.1088/1742-5468/abc7c7</a>'
  apa: 'De Nicola, S. (2021). Disentanglement approach to quantum spin ground states:
    Field theory and stochastic simulation. <i>Journal of Statistical Mechanics: Theory
    and Experiment</i>. IOP Publishing. <a href="https://doi.org/10.1088/1742-5468/abc7c7">https://doi.org/10.1088/1742-5468/abc7c7</a>'
  chicago: 'De Nicola, Stefano. “Disentanglement Approach to Quantum Spin Ground States:
    Field Theory and Stochastic Simulation.” <i>Journal of Statistical Mechanics:
    Theory and Experiment</i>. IOP Publishing, 2021. <a href="https://doi.org/10.1088/1742-5468/abc7c7">https://doi.org/10.1088/1742-5468/abc7c7</a>.'
  ieee: 'S. De Nicola, “Disentanglement approach to quantum spin ground states: Field
    theory and stochastic simulation,” <i>Journal of Statistical Mechanics: Theory
    and Experiment</i>, vol. 2021, no. 1. IOP Publishing, 2021.'
  ista: 'De Nicola S. 2021. Disentanglement approach to quantum spin ground states:
    Field theory and stochastic simulation. Journal of Statistical Mechanics: Theory
    and Experiment. 2021(1), 013101.'
  mla: 'De Nicola, Stefano. “Disentanglement Approach to Quantum Spin Ground States:
    Field Theory and Stochastic Simulation.” <i>Journal of Statistical Mechanics:
    Theory and Experiment</i>, vol. 2021, no. 1, 013101, IOP Publishing, 2021, doi:<a
    href="https://doi.org/10.1088/1742-5468/abc7c7">10.1088/1742-5468/abc7c7</a>.'
  short: 'S. De Nicola, Journal of Statistical Mechanics: Theory and Experiment 2021
    (2021).'
date_created: 2021-02-17T17:48:46Z
date_published: 2021-01-05T00:00:00Z
date_updated: 2023-08-07T13:46:28Z
day: '05'
ddc:
- '530'
department:
- _id: MaSe
doi: 10.1088/1742-5468/abc7c7
ec_funded: 1
external_id:
  isi:
  - '000605080300001'
file:
- access_level: open_access
  checksum: 64e2aae4837790db26e1dd1986c69c07
  content_type: application/pdf
  creator: dernst
  date_created: 2021-02-19T14:04:40Z
  date_updated: 2021-02-19T14:04:40Z
  file_id: '9172'
  file_name: 2021_JourStatMech_deNicola.pdf
  file_size: 1693609
  relation: main_file
  success: 1
file_date_updated: 2021-02-19T14:04:40Z
has_accepted_license: '1'
intvolume: '      2021'
isi: 1
issue: '1'
keyword:
- Statistics
- Probability and Uncertainty
- Statistics and Probability
- Statistical and Nonlinear Physics
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
  issn:
  - 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
status: public
title: 'Disentanglement approach to quantum spin ground states: Field theory and stochastic
  simulation'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2021
year: '2021'
...
---
_id: '7130'
abstract:
- lang: eng
  text: "We show that statistical criticality, i.e. the occurrence of power law frequency
    distributions, arises in samples that are maximally informative about the underlying
    generating process. In order to reach this conclusion, we first identify the frequency
    with which different outcomes occur in a sample, as the variable carrying useful
    information on the generative process. The entropy of the frequency, that we call
    relevance, provides an upper bound to the number of informative bits. This differs
    from the entropy of the data, that we take as a measure of resolution. Samples
    that maximise relevance at a given resolution—that we call maximally informative
    samples—exhibit statistical criticality. In particular, Zipf's law arises at the
    optimal trade-off between resolution (i.e. compression) and relevance. As a byproduct,
    we derive a bound of the maximal number of parameters that can be estimated from
    a dataset, in the absence of prior knowledge on the generative model.\r\n\r\nFurthermore,
    we relate criticality to the statistical properties of the representation of the
    data generating process. We show that, as a consequence of the concentration property
    of the asymptotic equipartition property, representations that are maximally informative
    about the data generating process are characterised by an exponential distribution
    of energy levels. This arises from a principle of minimal entropy, that is conjugate
    of the maximum entropy principle in statistical mechanics. This explains why statistical
    criticality requires no parameter fine tuning in maximally informative samples."
acknowledgement: We acknowledge interesting discussions with M Abbott, E Aurell, J
  Barbier, R Monasson, T Mora, I Nemenman, N Tishby and R Zecchina. This research
  was supported by the Kavli Foundation and the Centre of Excellence scheme of the
  Research Council of Norway (Centre for Neural Computation) (RJC and YR), by the
  Basic Science Research Program through the National Research Foundation of Korea
  (NRF), funded by the Ministry of Education (2016R1D1A1B03932264) (JJ), and, in part,
  by the ICTP through the OEA-AC-98 (JS).
article_number: '063402'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ryan J
  full_name: Cubero, Ryan J
  id: 850B2E12-9CD4-11E9-837F-E719E6697425
  last_name: Cubero
  orcid: 0000-0003-0002-1867
- first_name: Junghyo
  full_name: Jo, Junghyo
  last_name: Jo
- first_name: Matteo
  full_name: Marsili, Matteo
  last_name: Marsili
- first_name: Yasser
  full_name: Roudi, Yasser
  last_name: Roudi
- first_name: Juyong
  full_name: Song, Juyong
  last_name: Song
citation:
  ama: 'Cubero RJ, Jo J, Marsili M, Roudi Y, Song J. Statistical criticality arises
    in most informative representations. <i>Journal of Statistical Mechanics: Theory
    and Experiment</i>. 2019;2019(6). doi:<a href="https://doi.org/10.1088/1742-5468/ab16c8">10.1088/1742-5468/ab16c8</a>'
  apa: 'Cubero, R. J., Jo, J., Marsili, M., Roudi, Y., &#38; Song, J. (2019). Statistical
    criticality arises in most informative representations. <i>Journal of Statistical
    Mechanics: Theory and Experiment</i>. IOP Publishing. <a href="https://doi.org/10.1088/1742-5468/ab16c8">https://doi.org/10.1088/1742-5468/ab16c8</a>'
  chicago: 'Cubero, Ryan J, Junghyo Jo, Matteo Marsili, Yasser Roudi, and Juyong Song.
    “Statistical Criticality Arises in Most Informative Representations.” <i>Journal
    of Statistical Mechanics: Theory and Experiment</i>. IOP Publishing, 2019. <a
    href="https://doi.org/10.1088/1742-5468/ab16c8">https://doi.org/10.1088/1742-5468/ab16c8</a>.'
  ieee: 'R. J. Cubero, J. Jo, M. Marsili, Y. Roudi, and J. Song, “Statistical criticality
    arises in most informative representations,” <i>Journal of Statistical Mechanics:
    Theory and Experiment</i>, vol. 2019, no. 6. IOP Publishing, 2019.'
  ista: 'Cubero RJ, Jo J, Marsili M, Roudi Y, Song J. 2019. Statistical criticality
    arises in most informative representations. Journal of Statistical Mechanics:
    Theory and Experiment. 2019(6), 063402.'
  mla: 'Cubero, Ryan J., et al. “Statistical Criticality Arises in Most Informative
    Representations.” <i>Journal of Statistical Mechanics: Theory and Experiment</i>,
    vol. 2019, no. 6, 063402, IOP Publishing, 2019, doi:<a href="https://doi.org/10.1088/1742-5468/ab16c8">10.1088/1742-5468/ab16c8</a>.'
  short: 'R.J. Cubero, J. Jo, M. Marsili, Y. Roudi, J. Song, Journal of Statistical
    Mechanics: Theory and Experiment 2019 (2019).'
date_created: 2019-11-26T22:36:09Z
date_published: 2019-06-17T00:00:00Z
date_updated: 2021-01-12T08:11:57Z
day: '17'
doi: 10.1088/1742-5468/ab16c8
extern: '1'
external_id:
  arxiv:
  - '1808.00249'
intvolume: '      2019'
issue: '6'
keyword:
- optimization under uncertainty
- source coding
- large deviation
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1808.00249
month: '06'
oa: 1
oa_version: Preprint
publication: 'Journal of Statistical Mechanics: Theory and Experiment'
publication_identifier:
  issn:
  - 1742-5468
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
status: public
title: Statistical criticality arises in most informative representations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2019
year: '2019'
...