Coline Arnould

Vincent Rocher

Aldo S Bader

Emma Lesage

Nadine Puget

Thomas Clouaire

Raphael Mourad

Daan Noordermeer

Martin Bushell

Gaëlle Legube
email: gaelle.legube@univ-tlse3.fr

ATM-dependent formation of a novel chromatin compartment regulates the Response to DNA Double Strand Breaks and the biogenesis of translocations

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Main

DNA Double-Strand Breaks (DSBs) are highly toxic lesions that can trigger translocations or gross chromosomal rearrangements, thereby severely challenging genome integrity and cell homeostasis. Chromatin plays a pivotal function during DNA repair, which is achieved by either non-homologous end joining or homologous recombination pathways [START_REF] Clouaire | A Snapshot on the Cis Chromatin Response to DNA Double-Strand Breaks[END_REF] . Yet, little is known about the contribution of chromosome architecture into these processes. DSBs activate the DNA Damage Response (DDR) that largely relies on PI3K kinases, including ATM and DNA-PK, and on the establishment of megabase-sized, H2AX-decorated chromatin domains that act as seeds for subsequent signaling events, such as 53BP1 recruitment and DDR foci formation [START_REF] Rogakou | DNA Doublestranded Breaks Induce Histone H2AX Phosphorylation on Serine 139[END_REF][START_REF] Clouaire | Comprehensive Mapping of Histone Modifications at DNA Double-Strand Breaks Deciphers Repair Pathway Chromatin Signatures[END_REF] .

Importantly, H2AX spreading is largely influenced by the pre-existing chromosome conformation in topologically associating domains (TADs) [START_REF] Collins | DNA double-strand breaks induce H2Ax phosphorylation domains in a contact-dependent manner[END_REF][START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF][START_REF] Caron | Cohesin Protects Genes against γH2AX Induced by DNA Double-Strand Breaks[END_REF] and we recently reported that loop-extrusion, which compacts the chromatin and leads to TADs formation, is instrumental for H2AX spreading and DDR foci assembly [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . Moreover, irradiation induces a general chromatin response reinforcing TADs genome wide [START_REF] Sanders | Radiation-induced DNA damage and repair effects on 3D genome organization[END_REF] . At a larger scale, previous work in mammalian cells revealed that DSBs display the ability to "cluster" within the nuclear space (i.e., fuse) forming large microscopically visible repair foci, composed of several individual repair foci [START_REF] Aten | Dynamics of DNA Double-Strand Breaks Revealed by Clustering of Damaged Chromosome Domains[END_REF][START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF][START_REF] Roukos | Spatial Dynamics of Chromosome Translocations in Living Cells[END_REF] . DSB clustering depends on the actin network, the LINC (a nuclear envelope embedded complex) [START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF][START_REF] Lottersberger | 53BP1 and the LINC Complex Promote Microtubule-Dependent DSB Mobility and DNA Repair[END_REF][START_REF] Schrank | Nuclear ARP2/3 drives DNA break clustering for homology-directed repair[END_REF] , as well as on the liquid-liquid phase separation properties of 53BP1 [START_REF] Kilic | Phase separation of 53 BP 1 determines liquid-like behavior of DNA repair compartments[END_REF][START_REF] Pessina | Functional transcription promoters at DNA double-strand breaks mediate RNA-driven phase separation of damage-response factors[END_REF] . The function of DSB clustering has remained enigmatic given that juxtaposition of several DSBs can elicit translocation (i.e: illegitimate rejoining of two DNA ends) [START_REF] Roukos | Spatial Dynamics of Chromosome Translocations in Living Cells[END_REF] , questioning the selective advantage of DSB clustering/ repair foci fusion [START_REF] Guénolé | A meeting at risk: Unrepaired DSBs go for broke[END_REF] .

ATM drives an acute reinforcement of damaged TADs.

In order to get comprehensive insights into chromosome behavior following DSBs, we analyzed 3D genome organization using Hi-C data generated in the human DIvA cell line where multiple DSBs are induced at annotated positions upon hydroxytamoxifen (OHT) addition [START_REF] Iacovoni | High-resolution profiling of γH2AX around DNA double strand breaks in the mammalian genome[END_REF] . Our previous analyses using H2AX ChIP-seq and direct DSB mapping by BLESS allowed us to identify 80 robustly induced DSBs on the human genome [START_REF] Clouaire | Comprehensive Mapping of Histone Modifications at DNA Double-Strand Breaks Deciphers Repair Pathway Chromatin Signatures[END_REF] . Using differential Hi-C maps, we found that intra-TAD contacts frequencies were strongly increased within TADs that experience a DSB (i.e. damaged TADs, Fig. 1a, right panel red square) compared to undamaged TADs, while contacts with neighboring adjacent domains were significantly decreased (Fig. 1a, right panel blue square, Fig. 1b). Interestingly, in some instances, the DSB itself displayed a particularly strong depletion of contact frequency with adjacent chromatin (Fig. 1c black arrow) indicating that the DSB is kept isolated from the surrounding environment, outside of its own TAD.

We further investigated the contribution of PI3-Kinases involved in response to DSB by performing Hi-C in presence of inhibitors of ATM and DNA-PK, which respectively negatively and positively impact H2AX accumulation at DSBs (in contrast to ATR inhibition, which does not noticeably alter H2AX foci formation in DIvA cells) [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF][START_REF] Caron | Non-redundant Functions of ATM and DNA-PKcs in Response to DNA Double-Strand Breaks[END_REF] . Notably, DNA-PK inhibition exacerbated the increase in intra-TAD contacts following DSB induction, while ATM inhibition abrogated it (Fig. 1d, Fig. S1a). TAD structures visualized on Hi-C maps are believed to arise thanks to cohesin-mediated loop extrusion [START_REF] Fudenberg | Formation of Chromosomal Domains by Loop Extrusion[END_REF] . Our previous work indicated that a bidirectional, divergent, cohesin-dependent loop-extrusion process takes place at DSBs [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . This DSB-anchored loop extrusion can be visualized on differential Hi-C maps by a "cross" pattern centered on the DSB (Fig. 1e). Notably, ATM inhibition impaired loop extrusion, while DNA-PK inhibition strongly increased it (Fig. 1e). Moreover, depletion of the cohesin subunit SCC1, which abolishes DSB-induced loop extrusion [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] , decreased the reinforcement of intra TADcontacts in damaged, H2AX-decorated, chromatin domains (Fig. 1f, Fig. S1b).

Altogether these data indicate that ATM triggers cohesin-mediated loop extrusion arising from the DSB and the insulation of the damaged TADs from the surrounding chromatin.

ATM drives clustering of damaged TADs, in a cell cycle regulated manner

We further analyzed Hi-C data with respect to long-range contacts within the nuclear space. Hi-C data revealed that DSBs cluster together (Fig. 2a, red square away from the diagonal), as previously observed using Capture Hi-C [START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF] . The higher resolution of this Hi-C dataset now enables us to conclude that DSB clustering takes place between entire H2AX-decorated TADs and can happen between DSBs induced on the same chromosome (Fig. S2a) as well as on different chromosomes (Fig. S2b). Of interest, some H2AX domains were able to interact with more than a single other H2AX domain (Fig. 2b, black arrows). Notably, this ability to form clusters of multiples TADs (also known as TADs cliques [START_REF] Paulsen | Long-range interactions between topologically associating domains shape the four-dimensional genome during differentiation[END_REF] ) upon DSB induction correlated with several DSB-induced chromatin features that occur at the scale of an entire TAD [START_REF] Clouaire | Comprehensive Mapping of Histone Modifications at DNA Double-Strand Breaks Deciphers Repair Pathway Chromatin Signatures[END_REF] , including H2AX, 53BP1 and ubiquitin chains levels as well as the depletion of histone H1 around DSB detected by ChIP-seq (Fig. 2c). Moreover, it also correlated with initial RNAPII occupancy prior DSB induction indicating that DSBs prone to cluster and form damaged TAD cliques are those occurring in transcribed loci (Fig. 2c).

We further examined the effect of cohesin depletion on damaged TAD clustering. Inspection of individual DSBs indicated that SCC1 depletion by siRNA did not alter clustering (Fig. 2d).

Quantification of trans interactions between all DSBs also indicates that SCC1 depletion did not modify the ability of damaged TAD to physically interact together (Fig. S2c). Additionally, we found that inhibition of ATM compromised DSB clustering, whilst inhibiting DNA-PK activity triggered a substantial increase in DSB clustering (Fig. 2e, Fig. S2d).

Given the conflicting data regarding the cell cycle regulation of DSB clustering [START_REF] Aten | Dynamics of DNA Double-Strand Breaks Revealed by Clustering of Damaged Chromosome Domains[END_REF][START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF][START_REF] Schrank | Nuclear ARP2/3 drives DNA break clustering for homology-directed repair[END_REF] , we further investigated DSB clustering in synchronized cells. DSB clustering (i.e. damaged TAD-TAD interaction) could be readily detected by 4C-seq when using a DSB as a view point, as shown by the increase of 4C-seq signal observed on other DSBs induced on the genome (Fig. 2f). We used five individual view-points: one control view point located on an undamaged locus, and four viewpoints at DSBs sites, three of which being "cluster-prone" DSBs, and one efficiently induced DSB which is unable to cluster with other DSBs. 4C-seq experiments performed before and after DSB induction in synchronized cells indicated that DSB clustering is readily detectable during G1 and is strongly reduced during the other cell cycle stages (see an example Fig. S2e). G1-specific DSB clustering was observed only when using as viewpoints "clusteringprone" DSBs, but not when using the undamaged control locus or the DSB unable to cluster (Fig. 2g).

Taken altogether, our results indicate that upon DSB formation, TADs that carry DSBs are able to physically contact each other in the nuclear space (i.e. cluster) in a manner that is entirely dependent on ATM, exacerbated upon DNA-PK inhibition, and mostly independent of the cohesin complex. Damaged TAD clustering mostly takes place in G1 and correlates with TADscale DSB-induced chromatin modifications (H2AX, Ubiquitin accumulation and H1 depletion) as well as 53BP1 accumulation.

A new "D" sub-compartment forms following DSB induction

Previous work identified the existence of two main, spatially distinct, self-segregated, chromatin "compartments" in mammalian nuclei. These chromatin compartments were determined by Principal Component Analysis (PCA) of Hi-C chromosomal contact maps where the first principal component allowed to identify loci that share similar interaction pattern, and that can be visualized linearly using eigenvectors. Further correlations with epigenomic features revealed that these two spatially segregated compartments correspond to active (the "A" compartment or euchromatin) and inactive chromatin (the "B" compartment or heterochromatin) [START_REF] Lieberman-Aiden | Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome[END_REF] . The identification of A/B compartment using our Hi-C datasets revealed that DSB induction does not trigger major changes in genome compartmentalization into euchromatin versus heterochromatin (Fig. S3a). Saddle plots further confirmed that neither DSB treatment nor the pharmacological inhibition of DNAPK and ATM significantly modified the ability of the genome to segregate into active A and inactive B compartments (Fig. S3b).

Moreover, DSB induction did not generally lead to compartment switch of the underlying chromatin domain, except in very few cases: Among the 80 DSBs induced by AsiSI, 58 DSBs were induced in the A compartment and all of them remained in the A compartment following DSB induction (see an example Fig. S3c top panel). Conversely, among the 22 DSBs induced in the B compartment, only 4 showed a shift from B to A (see two examples Fig. S3c middle and bottom panels). We further investigated the relationship between the compartment type and the ability of DSBs to cluster together. Of interest, DSB clustering was detectable mostly for DSBs in the A compartment (Fig. S3d).

Beyond the main classification between A/B compartments, sub-compartments have since been identified using higher resolution Hi-C maps, which correspond to subsets of heterochromatin loci (B1-B4) and of active loci (A1-A2) [START_REF] Rao | A 3D Map of the Human Genome at Kilobase Resolution Reveals Principles of Chromatin Looping[END_REF] . Of interest, such sub-compartments also correspond to microscopically visible nuclear structures such as nuclear speckles (A1) [START_REF] Chen | Mapping 3D genome organization relative to nuclear compartments using TSA-Seq as a cytological ruler[END_REF] or Polycomb bodies (B1) [START_REF] Rao | A 3D Map of the Human Genome at Kilobase Resolution Reveals Principles of Chromatin Looping[END_REF] for instance. Given that previous studies have long identified large, microscopically detectable H2AX bodies following DNA damage and that our Hi-C data revealed clustering of damaged TADs, we postulated that DSBs may also induce a subcompartment, in particular within the A compartment (i.e,: some A compartment, damagedloci further segregate from the rest of the active compartment). In order to investigate this point, we applied PCA analysis on differential Hi-C maps (i.e. contact matrices of +DSB/-DSB) on each individual chromosome. The first Chromosomal Eigenvector (CEV, PC1) allowed us to identify a DSB-induced chromatin compartment mainly on chromosomes displaying a large number of DSBs (chr1,17 and X) (Fig. S4a, Fig. 3a,). Notably, a similar analysis on Hi-C maps generated upon DNA-PK inhibition, which impairs repair [START_REF] Caron | Non-redundant Functions of ATM and DNA-PKcs in Response to DNA Double-Strand Breaks[END_REF] and increases DSB clustering (Fig. 2), allowed to identify this compartment on more chromosomes (such as chr6 for instance, Fig. S4b, bottom track). This sub-compartment displayed a very strong correlation with H2AXdecorated chromatin following DSB (Fig. 3a, Fig. S4a-d) and was henceforth further named "D" sub-compartment (for DSB-induced compartment). Yet, further inspection revealed that the D sub-compartment is not solely generated through the clustering of damaged chromatin (i.e. TADs that carry DSBs and are enriched in H2AX). Indeed, we could identify chromatin domains, not containing any DSB and not decorated by H2AX, that associate with the D subcompartment after damage (blue rectangle Fig. 3b). After exclusion of H2AX-covered chromatin domains, correlation analysis using chromosomes 1,17 and X, on which the D subcompartment was readily detected, indicated that non-damaged loci that tend to segregate with the D compartment are enriched in H2AZac, H3K4me3 and H3K79me2 (Fig. S4e, Fig. 3b).

Conversely, these loci targeted to the D compartment displayed a negative correlation with repressive marks such as H3K9me3 (Fig. S4e). A similar trend was observed when D subcompartment was computed from the Hi-C data obtained in presence of the DNA-PK inhibitor and correlation analysis performed on all chromosomes showing D compartmentalization (i.e, chr 1,2,6,9,13,17,18,20 and X) (Fig. S4e bottom panel). Altogether our data indicate that upon DSB production on the genome, damaged TADs, covered by H2AX/53BP1, form a new chromatin compartment that segregates from the rest of the genome and in which some additional undamaged loci that exhibit chromatin marks typical of active transcription can be further targeted.

A subset of DNA damage responsive genes segregates with the D sub-compartment to achieve optimal activation.

In order to decipher the nature of the active genes targeted to the D compartment, we further explored the DNA motifs enriched on "D" genes compared to "non D" genes, i.e. genes recruited to the D compartment, versus the one that do not display targeting to the D compartment (discarding all genes directly comprised in H2AX domains). Notably, the top enriched motifs included OSR1, TP73, Nkx3.1 and E2F binding sites, which are tumor suppressor and /or known to be involved in the DNA damage response (Fig. S4f) [START_REF] Allocati | p63/p73 in the control of cell cycle and cell death[END_REF][START_REF] Fouad | E2F1: Cause and Consequence of DNA Replication Stress[END_REF][START_REF] Huang | Identification of p53 regulators by genome-wide functional analysis[END_REF][START_REF] Bowen | NKX3.1 Activates Cellular Response to DNA Damage[END_REF] , suggesting a direct physical targeting of DNA damage responsive genes to the "D" subcompartment. In agreement, visual inspection revealed that some known p53 target genes which are upregulated following DSB induction were associated with the D compartment, even when as far as >20MB from the closest DSB (see an example Fig. 3c). To test the hypothesis that DNA damage responsive genes are recruited to the D compartment, we performed RNA-seq before and after DSB induction and retrieved genes that are upregulated following DSB induction. Notably, genes upregulated following DSB induction displayed a higher D compartment signal compared to genes that were either not regulated or downregulated after DSBs (Fig. 3d). Of note, if some of the upregulated genes were indeed targeted to the D compartment, this was not the case for all of them. Importantly, the upregulated genes targeted to the D-compartment were not in average closer to DSBs than the upregulated genes nottargeted to the D compartment (Fig. S4g), ruling out a potential bias due to the genomic distribution of AsiSI DSBs.

In order to determine whether recruitment of those genes to the D sub-compartment contribute to their activation following DNA damage, we investigated the consequence of disrupting DSB clustering (and hence formation of D compartment) by depleting the SUN2 component of the LINC complex, previously found as a DSB-clustering promoting factor [START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF][START_REF] Lottersberger | 53BP1 and the LINC Complex Promote Microtubule-Dependent DSB Mobility and DNA Repair[END_REF] . SUN2 depletion altered the transcriptional activation of genes found to be upregulated and targeted to the D subcompartment upon DSB in DIvA cells (Fig. 3e).

Altogether these data indicate that DSB induction triggers the formation of a novel chromatin sub-compartment that comprises not only damaged TADs, decorated by H2AX and 53BP1, but also a subset of genes upregulated following DNA damage, for which targeting to D subcompartment is required for optimal activation. Altogether this suggests a role of the D subcompartment, and hence DSB clustering, in the activation of the DNA Damage Response.

DSB-induced reorganization of chromosome folding favors translocations.

Importantly, while our above data suggest a beneficial role of DSB clustering in potentiating the DDR, it may also be detrimental, since bringing two DSBs in a close proximity may fosters translocations (illegitimate rejoining of two DSBs), as previously proposed [START_REF] Roukos | Spatial Dynamics of Chromosome Translocations in Living Cells[END_REF] . We therefore assessed by qPCR the frequency of translocations events occurring in DIvA cells post-DSB induction, in conditions where we found altered DSBs clustering and D compartment formation.

Notably, translocations are increased in G1 compared to S/G2-synchronized cells (Fig. 4a), in agreement with an enhanced DSB clustering observed in G1 cells (Fig. 2). Moreover, DNA-PK inhibition, that increased D-compartment formation (Fig. 2e, Fig. S2d, Fig. S4b) also strongly increased translocation frequency (Fig. 4b). On another hand, depletion of 53BP1 (Fig. S5a), previously found to mediate repair foci phase separation [START_REF] Kilic | Phase separation of 53 BP 1 determines liquid-like behavior of DNA repair compartments[END_REF] , as well as a treatment with 1,6hexanediol, which disrupts phase condensates (Fig. S5b), decreased translocations (Fig. 4c).

Similarly, depletion of SUN2, member of the LINC complex and of ARP2, an actin branching factor (Fig. S5a), reported as mediating DSB clustering [START_REF] Aymard | Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes[END_REF][START_REF] Lottersberger | 53BP1 and the LINC Complex Promote Microtubule-Dependent DSB Mobility and DNA Repair[END_REF][START_REF] Schrank | Nuclear ARP2/3 drives DNA break clustering for homology-directed repair[END_REF] , decreased translocations (Fig. 4c). Surprisingly, depletion of the cohesin subunits SMC1 or SCC1 also decreased translocation frequency (Fig. 4d, Fig S5c). This was unexpected since SCC1-depleted cells do not display clustering defects (Fig. 2).

Given that the two translocations assessed by our qPCR assay are both intra-chromosomal translocations (i.e.: rejoining of two distant DSBs located on the same chromosome) we hypothesized that translocation frequency at the intra-chromosomal level may also be regulated by the DSB-induced loop extrusion that depends on the cohesin complex. In order to investigate more broadly translocation events between multiple DSBs induced in the DIvA cell line, we designed a novel multiplexed amplification protocol followed by NGS sequencing. In control cells, we could readily detect increased translocation frequency upon induction of DSB compared to control genomic locations (Fig. S5d). Strikingly, depletion of SCC1 decreased the frequency of intra-chromosomal translocations, while leaving inter-chromosomal translocations unaffected (Fig. 4e). In contrast depletion of SUN2 and ARP2 decreased both intra-and inter-chromosomal translocations (Fig. 4f-g). Taken together these data suggest that both the DSB-induced loop extrusion and the formation of the D sub-compartment through clustering of damaged TADs, display the potential to generate translocations.

Given our above finding that a subset of genes upregulated following DSB induction can be physically targeted to the D compartment after break induction (Fig. 3), we further hypothesized that such a physical proximity may account for some of the translocations observed on cancer genomes. We retrieved breakpoint positions of inter-chromosomal translocations of 1493 individuals across 18 different cancers types (from [START_REF] Zhang | A Pan-Cancer Compendium of Genes Deregulated by Somatic Genomic Rearrangement across More Than 1,400 Cases[END_REF] ), and assessed their potential overlap with genes targeted to the D sub-compartment (reproducibly detected in the three Hi-C replicates on chr1,17 and X, on which D sub-compartment could be identified accurately). D-targeted genes were further sorted as either upregulated, downregulated or not significantly altered following DSB induction, and compared to their counterparts not targeted to the D compartment. We found that genes that are upregulated following DSB induction and that are targeted to the D compartment displayed a significant overlap with translocations breakpoints, in contrast to genes that are not targeted to the D compartment (non-D) (Fig. 4h). Altogether these data indicate that the relocalization of upregulated genes during the DNA Damage response in the DSB-induced sub-compartment likely accounts for some of the translocations detected on cancer genomes. Given that DDR genes comprise a number of tumor suppressor genes, such a physical proximity of these genes with DSBs within the D sub-compartment formed in response to DNA damage, may be a key mechanism driving oncogenesis, through fostering the instability of tumor suppressor genes.

Conclusion

Altogether this work shows that DSB-induced changes in chromosome architecture is an integral component of the DNA Damage Response, but also acts as a double-edged sword that can challenge genomic integrity through the formation of translocations.

Our data suggest that a chromatin sub-compartment arises when H2AX/53BP1-decorated domains, established by ATM-induced loop extrusion post DSB, self-segregate from the rest of chromatin. This may, at least in part, occur thanks to the LLPS properties of 53BP1 [START_REF] Kilic | Phase separation of 53 BP 1 determines liquid-like behavior of DNA repair compartments[END_REF][START_REF] Pessina | Functional transcription promoters at DNA double-strand breaks mediate RNA-driven phase separation of damage-response factors[END_REF][START_REF] Spegg | Biomolecular condensates at sites of DNA damage: More than just a phase[END_REF] . This DSB-induced ("D") sub-compartment further recruits a subset of genes involved in the DNA damage response and contributes to their activation (Fig. S5e). This model is in agreement with previous work which identified 53BP1 as critical for p53 target genes activation [START_REF] Cuella-Martin | 53BP1 Integrates DNA Repair and p53-Dependent Cell Fate Decisions via Distinct Mechanisms[END_REF] , with the findings that disrupting 53BP1 droplet formation alters checkpoint activation [START_REF] Kilic | Phase separation of 53 BP 1 determines liquid-like behavior of DNA repair compartments[END_REF] and with the fact that enhanced 53BP1 phase separation triggers an elevated p53 response [START_REF] Ghodke | AHNAK controls 53BP1-mediated p53 response by restraining 53BP1 oligomerization and phase separation[END_REF] as does the loss of TIRR, a protein that regulates 53BP1 association to DSBs [START_REF] Drané | TIRR regulates 53BP1 by masking its histone methyl-lysine binding function[END_REF][START_REF] Parnandi | TIRR inhibits the 53BP1-p53 complex to alter cell-fate programs[END_REF] . We propose that the formation of the "D" sub-compartment allows to precisely tune the magnitude of the DDR with respect to DSB load and persistency, providing a function for these enigmatically large H2AX/53BP1decorated chromatin domains and to DSB clustering. Furthermore, this observation may provide a rationale for why so many transcription factors (including p53) were found recruited at DSBs repair foci [START_REF] Izhar | A Systematic Analysis of Factors Localized to Damaged Chromatin Reveals PARP-Dependent Recruitment of Transcription Factors[END_REF] . While initially thought to allow chromatin remodeling in order to enhance DSB repair, the recruitment of transcription factors to DSB repair foci may in fact rather reflects the relocalization of DDR genes within the D compartment (hence at physical proximity of the DSB).

Yet, this comes at the expense of potential translocations, as both loop extrusion and coalescence of damaged TAD are able to bring linearly distant DSBs in close physical proximity (Fig. S5e). Importantly, we found that the genes upregulated in response to DSB and relocated to the D compartment displayed significant overlap with translocation breakpoints identified by whole genome sequencing in patient cancer samples. In agreement with an increased occurrence of structural variants on tumor suppressor genes [START_REF] Zhang | A Pan-Cancer Compendium of Genes Deregulated by Somatic Genomic Rearrangement across More Than 1,400 Cases[END_REF] , we propose that the physical targeting of DNA damage responsive genes to the D compartment, by bringing DSBs and DDR genes in close spatial proximity, may occasionally trigger deleterious rearrangements on genes involved in the control of cell proliferation and apoptosis upon DNA damage, and may hence act as a critical driver of oncogenesis by disrupting the integrity of tumor suppressor genes.

Methods

Cell culture and treatments

DIvA (AsiSI-ER-U20S) [START_REF] Iacovoni | High-resolution profiling of γH2AX around DNA double strand breaks in the mammalian genome[END_REF] and AID-DIvA (AID-AsiSI-ER-U20S) 34 cells were grown in Dubelcco's modified Eagle's medium (DMEM) supplemented with 10% SVF (Invitrogen), antibiotics and either 1 µg/mL puromycin (DIvA cells) or 800 µg/mL G418 (AID-DIvA cells) at 37 °C under a humidified atmosphere with 5% CO2. To induce DSBs, cells were treated with 300nM 4OHT (Sigma, H7904) for 4 h. For ATM or DNA-PK inhibition, cells were pretreated for 1 h respectively with 20μM KU-55933 (Sigma, SML1109) or 2μM NU-7441 (Selleckchem, S2638) and during subsequent 4OHT treatment. Treatment with 10% 1,6-hexanediol (Sigma, 240117) was performed for 3 min before the end of the 4OHT treatment. For cell synchronization, cells were incubated for 18 h with 2 mM thymidine (Sigma, T1895), then released during 11 h, followed by a second thymidine treatment for 18 hr. S, G2 and G1 cells were then respectively treated with OHT at, 0, 6 or 11 h following thymidine release and harvested 4 h later. siRNA transfections were performed using the 4D-Nucleofector and the SE cell line 4D-Nucleofector X kit L (Lonza) according to the manufacturer's instructions, and subsequent treatment(s) were performed 48 h later. siRNA transfections were performed using a control siRNA (siCTRL): CAUGUCAUGUGUCACAUCU; or using a siRNA targeting

SCC1 (siSCC1): GGUGAAAAUGGCAUUACGG; or SMC1 (

Amplicon -seq

AID-DIvA cells were treated with or without 300nM 4OHT for 4 h followed by treatment with indole-3-acetic acid for 14 h. Cells were then lysed in cytoplasmic lysis buffer (50mM HEPES pH7.9, 10mM KCl2, 1.5mM MgCl2, 0.34M sucrose, 0.5% triton X-100, 10% glycerol, 1mM

DTT) for 10 minutes on ice, then washed once in cytoplasmic lysis buffer before lysis in genomic extraction buffer (50mM Tris pH8.0, 5mM EDTA, 1% SDS, 0.5mg/mL proteinase K).

Lysate was incubated at 60°C for 1 h. Genomic DNA was then ethanol precipitated on ice for 1h, pelleted at 19,000g for 20 min and washed twice in 75% ethanol. Genomic DNA was then used in a multiplex PCR reaction that amplified 25 target sites; 20 AsiSI cut sites and 5 uncut control sites (Supplementary Table 1). Amplicons were size selected using SPRIselect beads (Beckman, B23318) and subjected to DNA library preparation via the NEBNext Ultra II kit (NEB, E7645L). Libraries were pooled at equimolar concentrations and sequenced via an Illumina NextSeq 500 system using paired end 150 cycles. The data was analyzed via our custom tool mProfile, available at github.com/aldob/mProfile. This identified the genomic primers used in the original genomic PCR reaction to amplify each read in the pair. Translocated reads were therefore identified as those where each read in a pair was amplified by a different primer set, and this was normalized to the total reads that were correctly amplified by these primer sets.

RT-qPCR

RNA was extracted from fresh DIvA cells before and after DSB induction using the RNeasy kit (Qiagen). RNA was then reverse transcribed to cDNA using the AMV reverse transcriptase (Promega, M510F). qPCR experiments were performed to assess the levels of cDNA using REV: CCACATCTCTGTCGTCGTCC). cDNA levels were then normalized with RPLP0 cDNA level, then expressed at the percentage of the undamaged condition.

Immunofluorescence

DIvA cells were grown on glass coverslips and fixed with 4% paraformaldehyde during 15 min at room temperature. Permeabilization step was performed by treating cells with 0,5% Triton X-100 in PBS for 10 min then cells were blocked with PBS-BSA 3% for 30min. Primary antibodies targeting RNA PolI (Santa Cruz sc48385) or PML (Santa Cruz sc-966 (PG-M3))

were diluted 1:500 in PBS-BSA 3% and incubated with cells overnight at 4°C. After washes in 1X PBS, cells were incubated with anti-mouse secondary antibody (conjugated to Alexa 594 or Alexa 488, Invitrogen), diluted 1:1000 in PBS-BSA 3%, for 1h at room temperature. After a DAPI staining, Citifluor (Citifluor, AF-1) was used for coverslips mounting. Images were acquired with the software MetaMorph, using the 100X objective of a wide-field microscope (Leica, DM6000), equipped with a camera (DR-328G-C01-SIL-505, ANDOR Technology).

Western Blot

Western Blot experiments were performed as in 5 using primary antibody targeting SUN2

(Abcam ab124916 1:1000), ARP2 (Abcam ab128934 1:1000), 53BP1 (Novus Biologicals NB100-305 1:1000), SCC1 (Abcam ab992 1:500) or SMC1 (Abcam ab75819 1:1000).

RNA-seq

RNA-seq was performed as described in 35 . RNA-seq were mapped in paired-end to a custom human genome (hg19 merged with ERCC92) using STAR. Count matrices were extracted using htseq-count with union as resolution-mode and reverse strand mode. Differential expression analysis was made on the count matrix using edgeR with two replicates per condition and differential genes were determined with log-ratio test (LRT). Whole genome coverage was computed using deeptools and bamCoverage to generate bigwig using bam files (without PCR duplicate suppression). Using a cutoff of 0.1 for the adjusted p-value and 0.5 log2 fold-change (~41% increase/decrease of expression), we were able to determine 286 up-regulated and 125 down-regulated genes with 11 of them directly damaged by a DSB. Differential coverage between two conditions was performed using BamCompare from deeptools with setting binsize parameter at 50bp. Log2FC was calculated by edgeR in differential expression analysis.

4C-seq

4C-seq experiments performed in synchronized cells, before and after DSB induction were performed as in [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . Briefly, 10-15×10 [START_REF] Caron | Cohesin Protects Genes against γH2AX Induced by DNA Double-Strand Breaks[END_REF] DIvA cells per condition were cross-linked, lysed and digested with MboI (New England Biolabs). DNA ligation was performed using the T4 DNA ligase (HC) (Promega), and ligated DNA was digested again using NlaIII (New England Biolabs). Digested DNA was religated with the T4 DNA ligase (HC) (Promega) before to proceed to 4C-seq library preparation. 16 individual PCR reactions were performed in order to amplify ~800ng of 4C-seq template, using inverse primers including the Illumina adaptor sequences and a unique index for each condition (Supplementary Table 2). Libraries were pooled and sent to a Nextseq500 platform at the I2BC Next Generation Sequencing Core Facility (Gif-sur-Yvette).

4C-seq data were processed as described in [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . Briefly, bwa mem was used for mapping and samtools for sorting and indexing. A custom R script (https://github.com/bbcf/bbcfutils/blob/master/R/smoothData.R) was used to build the coverage file in bedGraph format, to normalize using the average coverage and to exclude the nearest region from each viewpoint. Differential 4C-seq data were computed using BamCompare from deeptools with binsize=50bp. Average of total Trans interactions between viewpoints and DSB were then computed using a 1Mb window around the breaks (80 best) and after exclusion of viewpoint-viewpoint (Cis) interactions.

Hi-C

Hi-C data obtained before and after DSB induction and upon CTRL or SCC1 depletion in DIvA cells were retrieved from [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . Hi-C experiments with or without DSB induction and upon ATM or DNA-PK inhibition were performed in DIvA cells as in [START_REF] Arnould | Loop extrusion as a mechanism for formation of DNA damage repair foci[END_REF] . Briefly, 1 million cells were used per condition. Hi-C libraries were generated using the Arima Hi-C kit (Arima Genomics) by following the manufacturer instructions. DNA was sheared to an average fragment size of 350-400 pb using the Covaris S220 and sequencing libraries were prepared on beads using the NEB Next Ultra II DNA Library Prep Kit for Illumina and NEBNext Multiplex Oligos for Illumina (New England Biolabs) following instructions from the Arima Hi-C kit.

Hi-C data analyses

Hi-C heatmaps. Hi-C reads were mapped to hg19 and processed with Juicer using default settings (https://github.com/aidenlab/juicer). Hi-C count matrices were generated using Juicer at multiple resolutions: 100 kb, 50 kb, 25 kb, 10 kb and 5 kb. Hi-C heatmaps screenshots were generated using Juicebox (https://github.com/aidenlab/Juicebox/wiki/Download). Aggregate heatmaps were computed on a set of sub-matrices extracted from originals observed Hi-C matrices at 50kb resolution or 100kb resolution. Region of 5Mb around DSBs (80 best) were extracted and then averaged. Log2 ratio was then computed using Hi-C counts (+DSB/-DSB) and plotted as heatmaps.

Cis Contacts Quantification. For cis contact quantification interaction within H2AX domains (-0.5/+0.5Mb around 80 best DSBs) were extracted from the observed Hi-C matrix at 100kb resolution, and log2 ratio was computed on damaged vs undamaged Hi-C counts (+DSB/-DSB).

Adjacent windows (-1.5Mb-0.5Mb and +0.5Mb-1.5Mb around 80 best DSBs) were retrieved to quantify interactions between damaged domains and adjacent undamaged domains.

Boxplots: Centre line, median; box limits, first and third quartiles; whiskers, maximum and minimum without outliers; points, outliers. Significance was calculated using non-parametric Wilcoxon test.

Trans contact quantification. To determine interaction changes in trans (inter-chromosomal)

we built the whole-genome Hi-C matrix for each experiment by merging together all chr-chr interaction matrices using Juicer and R. The result is a genome matrix with 33kx33k bin interactions for 100kb resolution. Interactions between bins inside damaged TADs (240X240 for 80 DSBs) were extracted and counted for each condition, log2 ratio was calculated on normalized count (cpm), and plotted as boxplots. Boxplots: Centre line, median; box limits, first and third quartiles; whiskers, maximum and minimum without outliers; points, outliers. Transcription factor motif analysis. TF-binding motifs were extracted on the promoter regions (-500bp/TSS) of genes with positive value of D compartment (2161) vs genes with negative value (2112) using motifmatchr and TFBSTools R packages on JASPAR2020 database. Motifs were sorted by significance using fisher exact test and adjusted with Benjamini-Hochberg procedure between motifs found on gene inside the D compartment versus genes outside D compartment.

Translocation breakpoints. For translocation breakpoints, data from [START_REF] Zhang | A Pan-Cancer Compendium of Genes Deregulated by Somatic Genomic Rearrangement across More Than 1,400 Cases[END_REF] were retrieved, and only breakpoints for interchromosomal structural variant selected (N=28051). Genes reproducibly enriched in Compartment D in the three biological replicates, on chr1, 17 and X (N=604) as well as genes not enriched in Compartment D (N=1439) were retrieved. The significance of the overlap between genes and breakpoints was determined using the regioneR package 36 using resampling test with PermTest. Briefly, we selected 1000 times a control set of genes, with same size and on the same chromosome as our original gene set. We tested the overlap between each genes and breakpoints, to determine a distribution of the number of overlaps between control set and breakpoints. We further tested if the overlap between our gene set (D compartment or non D compartment) and breakpoints was significant, by counting the number of times we got more overlap in control than in our gene set.

All high-throughput sequencing data (Hi-C, 4C-seq, Amplicon-seq and RNA-seq) have been deposited to Array Express (https://www.ebi.ac.uk/arrayexpress/) under accession number E-MTAB-XXXX. (f) As in (e) but the quantification was performed in SUN2 depleted cells (n=4 independent replicates).

(g) As in (e) but the quantification was performed in ARP2 depleted cells (n=4 independent replicates).

(h) Observed (green) and expected (obtained through 1000 permutations) overlap between breakpoint positions of inter-chromosomal translocations identified on cancer genomes and genes targeted to the D compartment, either upregulated, downregulated or not regulated following DSB induction (identified by RNA-seq) as indicated, compared to their counterparts not targeted to the D compartment.

  Translocation assays after siRNA transfection or 1,6-Hexanediol treatment were performed at least in triplicates in AID-DIvA cells as described in35 . Translocation assay in synchronized cells was performed in DIvA cells following a 4OHT treatment (n=4 biological replicates). Two different possible translocations between different AsiSI sites were assessed by qPCR using the : TCTGAAGTCTGCGCTTTCCA.Results were normalized using two control regions, both far from any AsiSI sites and γH2AX translocation frequencies were calculated using the Bio-Rad CFX Manager 3.1 software69.

  FAS (FW: ATGCACACTCACCAGCAACA; REV: AAGAAGACAAAGCCACCCCA) or GADD45A (FW: ACGATCACTGTCGGGGTGTA;

TAD

  Cliques. TAD Cliques were computed using the igraph R package on an undirected graph representing DSB clustering. This graph was computed on the differential Hi-C matrix (+DSB/-DSB) counts, at 500 kb resolution, considering a change of ~86% of interaction (0.9 in log2) as between two DSBs as a node on the graph. Averaged signal of ChIP-seq values (53BP1/H2AX/H1/Ubiquitin FK2) were then computed for each categories of cliques using 500kb windows around DSB. For prior RNAPII occupancy, the signal was computed on 10kb around DSBs. A/B compartment. To identify the two mains chromosomal compartments (A/B), the extraction of the first eigenvector of the correlation matrix (PC1) was done on the Observed/Expected matrix at 500kb resolution using juicer eigenvector command. The resulting values were then correlated with ATAC-seq signal in order to attributes positives and negatives values to the A and B compartment, respectively, on each chromosomes. The Observed/Expected bins were arranged based on the PC1 values and aggregated into 21 percentiles, to visualize A-B interactions on our experiments (saddle plots). D compartment. To identify the D compartment, we retrieved the first component (PC1) of a PCA made on the differential observed Hi-C matrix 𝑙𝑜𝑔2 ( 𝑑𝑎𝑚𝑎𝑔𝑒𝑑 𝑢𝑛𝑑𝑎𝑚𝑎𝑔𝑒𝑑 ) at 100kb resolution. Each matrix was extracted from the .hic files using Juicer and the ratio was computed bin per bin. Pearson Correlation matrices were then computed for each chromosome, and PCA was applied on each matrix. The first component of each PCA was then extracted and correlated with the positions of DSB. A PC1 showing a positive correlation with DSB was then called D compartment, and PC1 showing negative correlation with DSBs were multiplied by -1. We were able to extract the D compartment on chromosomes 1,17 and X for +DSB/-DSB and chromosomes 1,2,6,9,13,17,18,20 and X for +DSB/-DSB in DNA-PKi condition. D compartment (first component of the PCA) was converted into a coverage file using rtracklayer R package. Using the same package, D compartment value was computed around DSBs and genes at 100kb resolution, and plotted as boxplot. Boxplots: Centre line, median; box limits, first and third quartiles; whiskers, maximum and minimum without outliers; points, outliers.

Figure 1 :

 1 Figure 1: Cohesin and ATM-dependent TAD reinforcement in response to DSBs.

Figure 2 :

 2 Figure 2: Cell cycle regulated, ATM-dependent but cohesin-and DNA-PK-independent

Figure 3 .

 3 Figure 3. Formation of a DSB-specific sub-compartment that ensures optimal activation

Figure 4 .

 4 Figure 4. DSB-induced loop extrusion and D-compartment formation drive

  Transcriptionally active chromatin recruits homologous recombination at DNA double-strand breaks. Nat. Struct. Mol. Biol. 21, 366-374 (2014). 35. Cohen, S. et al. Senataxin resolves RNA:DNA hybrids forming at DNA double-strand

	breaks to prevent translocations. Nat. Commun. 9, 533 (2018).
	36. Gel, B. et al. regioneR: an R/Bioconductor package for the association analysis of
	genomic regions based on permutation tests. Bioinformatics btv562 (2015)
	doi:10.1093/bioinformatics/btv562.

32 34. Aymard, F. et al.

Acknowledgments

We thank the genomics core facility of EMBL and of the I2BC (Centre de Recherche de Gif) for high-throughput sequencing. M.B. was supported by the CRUK Beatson Institute core grant A29252; A.B was supported by national productivity award from the MRC, MC_ST_U17040. Funding in GL laboratory was provided by grants from the European Research Council (ERC-2014-CoG 647344), Agence Nationale pour la Recherche (ANR-18-CE12-0015) and the Ligue Nationale contre le Cancer (LNCC). C.A was a recipient of a FRM fellowship (FRM FDT201904007941). T.C and N.P are INSERM researchers.

Data Availability

Code availability

Source codes are available from https://github.com/LegubeDNAREPAIR/

Authors contributions

Competing Interest

The authors declare no competing interest


Thibault Lesieur

Léo Miolane

Marc Lelarge

Florent Krzakala

Lenka Zdeborová

Statistical and computational phase transitions in spiked tensor estimation

teaching and research institutions in France or abroad, or from public or private research centers.

1 The spiked tensor model One observes an order-p tensor Y ∈ p R N created as

Y = (p -1)! N p-1 2 r k=1 (X 0 k ) ⊗p + V , (1)
where X 0 1 , . . . , X 0 r ∈ R N are r unknown vectors to be inferred from Y , and V ∈ p R N is a symmetric tensor accounting for noise. We denote by X the N ×r matrix that collects the r vectors X k . The observed tensor Y can thus be seen as a rank r perturbation of a random symmetric tensor V . Consider now the setting where the X 0 is generated at random from a known prior distribution. The core question considered in this paper is: What is the best possible reconstruction of X 0 one can hope for?

In fact, we can look at even more general noise than just additive one as in [START_REF] Michael Aizenman | Extended variational principle for the Sherrington-Kirkpatrick spin-glass model[END_REF]. Denote for i = 1, . . . , N , x i = (x i,1 , . . . , x i,r ) ∈ R r the r-dimensional vector created by aggregating the i th coordinates of the r vectors X k . Assume that for 1 ≤ i ≤ N the x 0 i are generated independently from a probability distribution P X over R r . We denote, for (i 1 , i 2 , . . . , i p ) ∈ {1, . . . , N } p W 0 i 1 ,i 2 ,...,ip = (p -1)!

N p-1 2 r k=1 x 0 i 1 ,k x 0 i 2 ,k • • • x 0 ip,k . (2)
For simplicity, we will assume to only observe the extra-diagonal elements of Y , i.e. the coe cients Y i 1 ,i 2 ,...,ip for 1 ≤ i 1 < • • • < i p ≤ N . The case where all coe cients are observed can be directly deduced from this case. The observed tensor Y is generated from W 0 using a noisy component-wise output channel P out so that

P (Y |X 0 ) = i 1 <i 2 <•••<ip P out Y i 1 ,i 2 ,...,ip W 0 i 1 ,i 2 ,...,ip . (3)
The simplest situation corresponds to eq. ( 1) with additive white Gaussian noise (AWGN), i.e. P out ( • | w) = N (w, ∆).

Given the above generative model and assuming that both the prior distribution P X and the output channel P out are known we can write the Bayes-optimal estimator of X 0 as marginalization of the following posterior distribution

P (X|Y ) = 1 Z N N i=1 P X (x i ) i 1 <i 2 <•••<ip P out Y i 1 ,i 2 ,...,ip W i 1 ,i 2 ,...,ip , (4)
where Z N is a normalization constant depending of the observed tensor Y , W i 1 ,i 2 ,...ip is de ned analogously to (2) (with X instead of X 0 ). We will study this tensor estimation problem in the limit where the dimension N → ∞ while the rank r remains constant. The factor N p- 1 2 is here to ensure that information-theoretically the inference problem is neither trivially hard nor trivially easy when one deals with signals such that x i and the noise magnitude are of order 1. The factor (p -1)! is used for convenient rescaling of the signal-to-noise ratio.

Related work and summary of results

Recently there have been numerous works on the matrix (p = 2) version of the above setting. In particular an explicit single-letter characterization of the mutual information and of the optimal Bayesian reconstruction error have been rigorously established [START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Deshpande | Information-theoretically optimal sparse PCA[END_REF][START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF][START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF]. A large part of these results rely on the approximate message passing (AMP) algorithm. For the rank-one matrix estimation problems AMP has been introduced by [START_REF] Rangan | Iterative estimation of constrained rank-one matrices in noise[END_REF], who also derived the state evolution (SE) formula to analyze its performance, generalizing techniques developed by [START_REF] Bayati | The dynamics of message passing on dense graphs, with applications to compressed sensing[END_REF]. In [START_REF] Lesieur | MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel[END_REF][START_REF] Lesieur | Phase transitions in sparse PCA[END_REF][START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] the generalization to larger rank, and general output channel, was considered. Following the theorem proven in [START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Deshpande | Information-theoretically optimal sparse PCA[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF], we know that indeed AMP is Bayes-optimal and achieves the minimum mean-squared error (MMSE) for a large set of parameters of the problem. There, however, might exist a region denoted as hard, where this is not the case, and polynomial algorithms improving on AMP are not known.

In comparison, there has been much less work on Bayesian low-rank tensor estimation. In statistical physics, the measure (4) was considered for Y with random i.i.d. components. For a Gaussian P X , it is called the spherical p-spin glass [START_REF] Crisanti | The spherical p-spin interaction spin glass model: The statics[END_REF], while for Rademacher P X it is the Ising p-spin glass [START_REF] Mézard | Spin-Glass Theory and Beyond[END_REF]. AMP for tensor estimation is actually equivalent to the so-called Thouless-Anderson-Palmer equations in spin glass theory [START_REF] Crisanti | Thouless-anderson-palmer approach to the spherical p-spin spin glass model[END_REF][START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF][START_REF] Thouless | Solution of 'solvable of a spin glass[END_REF]. In the context of tensor PCA these equations have been studied by Richard and Montanari [START_REF] Richard | A statistical model for tensor PCA[END_REF] for the maximum likelihood estimation. Interestingly, they showed that the hard phase was particularly large in the tensor estimation case and that, with side information (such that for each component x i,k we have its direct noisy observation), the estimation problem becomes easier. However, such a kind of component-wise side information is very strong and rarely available in applications. The tight statistical limits for the present tensor model were also studied in [START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF] for the special case of the Rademacher (Ising) prior. For more generic priors only upper and lower bounds are known rigorously [START_REF] Perry | Statistical limits of spiked tensor models[END_REF].

Summary of results:

In this contribution, we aim to bridge the gap between what is known for the general r, P x , P out Bayesian estimation for low-rank matrices and what is known for low-rank tensors. We present the following contributions:

(A) The AMP algorithm and its state evolution analysis for the Bayes-optimal tensor estimation, see sections 3 and 4. (B) The so-called channel universality result that allows us to map any generic channel P out on a model with additive Gaussian noise, see section 3. (C) Rigorous formula for the asymptotic mutual information and the MMSE, thus generalizing the matrix results of [START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF], see section 5. (D) The identi cation of statistical and computational phase transitions. In fact, we show that as soon as the e ect of a non-zero-mean prior is taken properly into account, the hard region shrinks considerably, making the tensor decomposition problem much easier than hitherto believed, at least for algorithms that do take the prior information into account. Having a reliable prior information on the distribution of x i (not on each of the components as in [START_REF] Richard | A statistical model for tensor PCA[END_REF]) is rather realistic in applications, for instance when constraints of negativity or membership to clusters are imposed. This is presented in sections 4 and 6.

AMP algorithm & channel universality

We discuss in this section the Approximate Message Passing (AMP) algorithm for the Bayesian version of the problem. This is a relatively straightforward generalization of what has been done for the low-rank matrix estimation in e.g. [START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF][START_REF] Matsushita | Low-rank matrix reconstruction and clustering via approximate message passing[END_REF][START_REF] Rangan | Iterative estimation of constrained rank-one matrices in noise[END_REF], i.e. p = 2 case of the present setting. In general, AMP is derived from belief propagation by taking into account that every variable in the corresponding graphical model has a large number of neighbors. Since the incoming messages are considered independent one can use the central limit theorem and represent each message as a Gaussian with a given mean xi ∈ R r and covariance σ i ∈ R r×r . A crucial property, called channel universality, that the tensor-AMP shares with the low-rank matrix estimation, allows to drastically simplify the problem of tensor estimation with generic output channel P out . The justi cation of this property follows closely the low-rank matrix estimation case, and we refer the reader to [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF][START_REF] Lesieur | MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel[END_REF][START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF]. First, we de ne the Fisher score tensor S associated to the output channel P out and its Fisher information ∆ as

S ≡ ∂ log P out (Y, w) ∂w w=0 , (5)
1 ∆ ≡ E Y ∼Pout(• | 0) ∂ log P out (Y, w) ∂w 2 w=0 . ( 6
)
where it is understood in (5) that the function y → ∂ log Pout(y,w) ∂w w=0 acts component-wise on Y . Informally speaking, the channel universality property states that the mutual information of the problem de ned by the output channel P out is the same as the one of a AWGN (1) with variance ∆, and that the AMP algorithm written for the Bayes-optimal inference of low-rank tensors then depends on the data tensor Y and the output channel P out only trough the tensor S and the e ective noise ∆.

AMP involves an auxiliary function that depends explicitly on the prior as follows. De ne the probability distribution

M(x) = 1 Z X (A, B) P X (x)e B x-x Ax 2 , (7)
where Z X (A, B) is a normalization factor. Then AMP uses the function f in (A, B) ∈ R r , A ∈ R r×r , B ∈ R r de ned by the expectation f in (A, B) = E M(x) [x] as well as the covariance matrix ∂ B f in (A, B). We shall denote the

overlap of u = (u 1 , . . . u N ), v = (v 1 , . . . v N ) ∈ (R r ) N by u • v = 1 N n j=1 u j v j ∈ R r×r .
AMP is then written as an iterative update procedure on the estimates of the posterior means and co-variances xi and σ i that uses auxiliary variables B i ∈ R r and A ∈ R r×r :

B t i = (p -1)! N p-1 2 i 2 <i 3 <•••<ip S i,i 2 ,i 3 •••ip xt i 2 • xt i 3 • • • • • xt ip - (p -1) ∆ 1 N N j=1 σ t j • (x t • xt-1 ) •(p-2) xt-1 i ( 8
)
A t = 1 ∆ (x t • xt ) •(p-1) (9)
xt+1 i = f in (A t , B t i ) (10)
σ t+1 i = ∂ B f in (A t , B t i ) , (11)
where • denotes a component-wise (Hadamard) product of matrices, and x •p the corresponding componentwise power.

4 Theoretical analysis

State evolution of AMP

The evolution of the AMP algorithm in the limit of large systems N → ∞ can be tracked via a low-dimensional set of equations called the state evolution (SE). For maximum-likelihood estimation the state evolution have been used in [START_REF] Richard | A statistical model for tensor PCA[END_REF]. Its heuristic derivation for the present case of general rank r, prior P X , and output P out follows line by line the matrix estimation case detailed in [START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF].

For the Bayes-optimal inference, SE is written in terms of an order parameter M t ∈ R r×r describing the overlap between xt (the AMP estimator at iteration t) and the ground truth x 0 de ned as M t = xt • x 0 , and reads

M t+1 = E Z,x 0 f in M t , M t x 0 + M t 1/2 Z x 0 , (12)
M t = (M t ) •(p-1) /∆ , (13)
where Z ∼ N (0, I r ) and x 0 ∼ P X are independent. M •(n) is again the n-th Hadamard power of a matrix M .

We shall not present a rigorous proof of the SE for tensor estimation and rely instead on standard arguments from statistical physics. The performance of the AMP algorithm can be understood by initializing the SE at M t=0 = 0. Or when M = 0 is a xed point of SE we initialize as M t=0 = , an in nitesimally small number (accounting for the fact that a random initialization of AMP will -due to nite size uctuationsbe in nitesimally correlated with the ground truth). We denote M AMP the xed point of the state evolution resulting from iterations of (12-13) from this initialization. The mean-squared error achieved by tensor-AMP is then

MSE AMP = Tr [Σ X -M AMP ] . (14)
where

Σ X = E x [xx ].
When P X has zero mean, this is the covariance matrix of P X .

Information-theoretically optimal inference

Our next goal is to analyze the performance of (possibly intractable) Bayes-optimal inference that evaluates the marginals of the posterior probability distribution (4). The error achieved by this procedure will be denoted the minimum mean-squared error (MMSE) and is formally de ned as

MMSE N = inf θ 1 N E X 0 -θ(Y ) 2 = 1 N E X 0 -E[X 0 |Y ] 2 ,
where the in mum is taken over all measurable functions θ of Y . In order to compute the MMSE it is instrumental to compute the mutual information I(X 0 ; Y ). This quantity is related to the free energy from statistical physics (see section 5 and [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF]). To compute the limit of such quantities, one traditionally applies the replica method stemming from statistical physics [START_REF] Mézard | Spin-Glass Theory and Beyond[END_REF]. We take advantage of the fact that for the Bayesoptimal inference the so-called replica symmetric version of this method yields the correct free energy [START_REF] Zdeborová | Statistical physics of inference: Thresholds and algorithms[END_REF].

The replica method yields

1 N I(X 0 ; Y ) ----→ N →∞ 1 2p∆ r k,k =1 (Σ X ) p k,k -sup M ∈S + r φ RS (M ) , (15)
φ RS (M ) = E Z,x 0 log Z X M , M x 0 + M 1/2 Z - p -1 2p∆ r k,k =1 M p kk (16)
where M = M •(p-1) /∆, Z X (A, B) is de ned in eq. ( 7), x 0 ∼ P X and Z ∼ N (0, I r ) are independent random variables. S + r denotes the set of r × r symmetric positive semi-de nite matrices. In section 5 we prove this result for the rank-one case (r = 1).

The replica free energy ( 16) not only provides the limit of the mutual information I(X 0 ; Y ), but thanks to an "I-MMSE Theorem" (similar to [START_REF] Guo | Mutual information and minimum mean-square error in gaussian channels[END_REF]) it yields the value of the MMSE for tensor estimation, see sec. 5.

Denoting M * = argmax M φ RS (M ) we get MMSE = lim N →∞ MMSE N = Tr [Σ X -M * ] . (17)
We proved [START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] rigorously, but only in the rank-one case and for odd values of p, see again sec. 5. Notice that when r ≥ 2 the estimation problem is symmetric under permutations of the r columns of X 0 : [START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF] is not expected to be true without further assumptions.

Statistical and computational trade-o

By evaluation of the derivative of [START_REF] Lesieur | Phase transitions in sparse PCA[END_REF] with respect to M one can check that critical points of ( 16) are xed points of the state evolution equations (12-13) allowing all the results to be read of the curve φ RS (M ): The global maximum of [START_REF] Lesieur | Phase transitions in sparse PCA[END_REF] gives the MMSE while the (possibly local) maximum reached by iteration of (12-13) from the uninformative initialization yields the MSE AMP . We now discuss the interplay between the MMSE and MSE AMP . The working hypothesis in this paper is that AMP yields lowest MSE among known polynomial algorithms. Depending on the parameters of model (4), i.e. the order of the tensor p, rank r, prior distribution P X , and output channel P out that appears in the SE only via its Fisher information ∆, we can distinguish between two cases: the easy phase where asymptotically AMP is Bayes optimal so that MMSE = MSE AMP , and the hard phase where MMSE < MSE AMP .

Given both the MMSE and MSE AMP are non-decreasing in ∆ we denote the borders of the hard phase (when it exists) as follows: Information theoretic threshold ∆ IT as the (limsup of the) highest ∆ for which MMSE < MSE AMP . Algorithmic threshold ∆ Alg as the (liminf of the) lowest ∆ for which MMSE < MSE AMP . Another threshold used in this paper is that of a critical value ∆ c de ned as smallest ∆ such that for ∆ > ∆ c one has M AMP = M * (∆ = +∞) (the estimate one can do when the noise is in nite), and for ∆ < ∆ c one has M AMP > M * (∆ = +∞). Note that from the de nition we must have ∆ c ≥ ∆ Alg . In cases where the hard phase does not exist, but ∆ c < ∞ we will consider that ∆ c = ∆ IT = ∆ Alg .

Existing results on maximum likelihood estimation [START_REF] Richard | A statistical model for tensor PCA[END_REF] suggest that for tensor decomposition p ≥ 3 we have ∆ Alg = ∆ c = 0 in the limit N → 0 considered in this paper. This means that the spiked model of low-rank tensor decomposition is algorithmically very hard, compared to matrix p = 2 case. The authors of [START_REF] Richard | A statistical model for tensor PCA[END_REF] give a good account on how ∆ needs to scale with N for known polynomial algorithms to work.

For the Bayes-optimal estimation the situation seems at rst sight similar. Indeed, whenever the prior P X has a zero mean, for p ≥ 3 we get ∆ Alg = ∆ c = 0 and the hard phase is consequently huge. This can be seen as follows. Indeed if the mean of the prior P X is zero then the state evolution equations (12-13) have a xed point M = 0. Expanding the state evolution around this xed point we nd

M t+1 = 1 ∆ Σ X (M t ) •(p-1) Σ X . (18)
Whenever p ≥ 3 the xed point M = 0 is stable for all ∆ > 0. Hence ∆ Alg = ∆ c = 0 for priors of zero mean.

A closer look, however, shows that the situation is not so pessimistic. Indeed, as soon as the mean of the prior P X is non-zero, M = 0 is no longer a xed point of the state evolution and once we solve the state evolution equations we observe either ∆ Alg > 0 (with AMP performing optimally for ∆ < ∆ Alg ) or the hard phase is completely absent and AMP has information-theoretically optimal performance for all ∆. We give examples of such priors in section 6.

Rigorous results

We present in this section rigorous results for the rank-one case (r = 1). As mentioned above, the universality property [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF][START_REF] Lesieur | MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel[END_REF] reduces the computation of the mutual information to the case of additive white Gaussian noise.

Consider a probability distribution P X over R that admits a nite second moment Σ X . The observation model (1) reduces in the rank-one case to

Y i 1 ,...,ip = (p -1)! N (p-1)/2 x 0 i 1 . . . x 0 ip + V i 1 ,...,ip for 1 ≤ i 1 < • • • < i p ≤ N,
where

X 0 = (x 0 1 , . . . , x 0 N ) i.i.d. ∼ P X and (V i 1 ,...,ip ) i 1 <•••<ip i.i.d.
∼ N (0, ∆) are independent. We de ne the Hamiltonian

H N (X) = ∆ -1 i 1 <•••<ip (p -1)! N (p-1)/2 Y i 1 ,...,ip x i 1 . . . x ip - (p -1)! 2N p-1 x i 1 . . . x ip 2 , (19)
for X = (x 1 , . . . , x N ) ∈ R N . We also write dP X (X) = N i=1 dP X (x i ). The posterior distribution (4) of X 0

given Y reads then:

dP (X 0 = X|Y ) = 1 Z N dP X (X)e H N (X) , (20)
where Z N is the appropriate normalizing factor. Then the free energy is de ned as (minus) the logarithm of Z N of the Boltzmann probability divided by N and averaged over Y . This is of particular interest since it is related to the mutual information (see [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF]):

I(X 0 ; Y ) = N 2p∆ Σ p X -E[log Z N ] + O(1) .
In the rank-one case, the expression ( 16) of φ RS simpli es, so that we will use in this section

φ RS : m ≥ 0 → E log dP X (x) exp m p-1 ∆ Zx + m p-1 ∆ xx 0 - m p-1 2∆ x 2 - p -1 2p∆ m p , ( 21
)
where E is the expectation with respect to the independent random variables x 0 ∼ P X and Z ∼ N (0, 1).

The proof of ( 15) reduces then to the following Theorem.

Theorem 1 (Replica-symmetric formula for the free energy). Let P X be a probability distribution over R, with nite second moment. Then, for all ∆ > 0

F N ≡ 1 N E [log Z N ] ----→ N →∞ sup m≥0 φ RS (m) ≡ F RS (∆) . (22)
We now de ne the tensor-MMSE, T-MMSE N by

T-MMSE N (∆) = inf θ    p! N p i 1 <•••<ip x 0 i 1 . . . x 0 ip -θ(Y ) i 1 ...ip 2    ,
where the in mum is taken over all measurable functions θ of the observations Y . Let us write λ = 1 ∆ . Using an "I-MMSE Theorem" (see [START_REF] Guo | Mutual information and minimum mean-square error in gaussian channels[END_REF]) and the fact that the tensor MMSE is achieved by the posterior mean of (X 0 ) ⊗p given Y , it is not di cult to verify that

∂F N ∂λ = N (N -1) . . . (N -p + 1) 2pN p Σ p X -T-MMSE N (∆) .
The arguments are the same than in the matrix (p = 2) case, see [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] Corollary 17. T-MMSE(∆) increases with the noise level ∆, so that ∂ ∂λ F N is a non-decreasing function of λ. F N is thus a convex function of λ, and so is F RS its pointwise limit. Consequently, ∂ ∂λ F N → ∂ ∂λ F RS at all values of λ at which F RS is di erentiable, that is for almost every ∆ > 0. For these values of ∆, one can also verify that the maximizer m * of φ RS is unique: we refer to [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] for a detailed proof in the matrix case p = 2. We thus obtain the following theorem:

Theorem 2 (Tensor-MMSE). For almost every ∆ > 0, φ RS admits a unique maximizer m * (∆) over R + and

T-MMSE N ----→ N →∞ Σ p X -m * (∆) p .
The information-theoretic threshold ∆ IT is the maximal value of ∆ such that lim T-MMSE N < Σ p X -E P X [x] 2p (which is the asymptotic performance achieved by random guess). We obtain thus the precise location of the information-theoretic threshold:

∆ IT = sup ∆ > 0 m * (∆) > E P X [x] 2 .
Let X = (x 1 , . . . , x N ) be a sample from the posterior (4), independently of everything else. An extension of Theorem 2 of [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] (that was derived for priors P X with bounded support) to the tensor case, gives that for almost every ∆ > 0,

E 1 N N i=1 x 0 i x i p -m * (∆) p ----→ N →∞ 0 , (23)
i.e. the p th -power of the overlap X • X 0 concentrates around m * . This leads to Theorem 3 (Vector-MMSE for odd p). Suppose that P X has a bounded support. If p is odd, then for almost every

∆ > 0 MMSE N ----→ N →∞ Σ X -m * (∆).
Before showing how [START_REF] Rangan | Iterative estimation of constrained rank-one matrices in noise[END_REF] implies Theorem 3 we need to introduce a fundamental property of Bayesian inference: the Nishimori identity.

Proposition 1 (Nishimori identity). Let (X, Y ) be a couple of random variables on a polish space. Let k ≥ 1 and let X (1) , . . . , X (k) be k i.i.d. samples (given Y ) from the distribution P (X = • | Y ), independently of every other random variables. Let us denote • the expectation with respect to P (X = • | Y ) and E the expectation with respect to (X, Y ). Then, for all continuous bounded function f E f (Y, X (1) , . . . , X (k) ) = E f (Y, X (1) , . . . , X (k-1) , X) .

Proof. It is equivalent to sample the couple (X, Y ) according to its joint distribution or to sample rst Y according to its marginal distribution and then to sample X conditionally to Y from its conditional distribution P (X = • | Y ). Thus the (k + 1)-tuple (Y, X (1) , . . . , X (k) ) is equal in law to (Y, X (1) , . . . , X (k-1) , X).

We will now use Proposition 1 to prove Theorem 3.

Proof of Theorem 3. Let • denote the expectation with respect to the posterior distribution P (X 0 = • | Y ), and let X be a sample from this distribution, independently of everything else. The best estimator of X 0 in term of mean-squared error is the posterior mean X = ( x 1 , . . . , x N ). Therefore

MMSE N = 1 N E N i=1 (x 0 i -x i ) 2 = 1 N E N i=1 (x 0 i ) 2 + x i 2 -2 x 0 i x i = Σ X + E X • X -2E X 0 • X ,
where X is another sample from • , independently of everything else. We apply now the Nishimori identity (Proposition 1) to obtain

E X • X = E X 0 • X . This gives MMSE N = Σ X -E X • X 0 .
We then deduce from ( 23) that E X • X 0 ----→ N →∞ m * , because p is here supposed to be odd. This concludes the proof.

We will now prove Theorem 1. For the matrix case (p = 2), this has been proved in [START_REF] Barbier | Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula[END_REF][START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] and we explain here how this can be adapted to the case p ≥ 2. To prove the limit [START_REF] Perry | Statistical limits of spiked tensor models[END_REF], one shows successively an upper bound on lim sup F N and the matching lower bound on lim inf F N . As shown in [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] (Section 6.2.2) one only need to prove Theorem 1 for input distributions P X with nite support S. We now assume to be in this situation.

Adding a small perturbation

One of the key ingredient of the proof is the introduction of a small perturbation of our model, that takes the form of a small amount of side information. This kind of techniques are frequently used for the study of spin glasses, where these small perturbations forces the Gibbs measure to verify some crucial identities, see [START_REF] Panchenko | The Sherrington-Kirkpatrick model[END_REF]. In our context of Bayesian inference, we will see that small quantities of side information "breaks" the correlations of the signal variables under the posterior distribution.

Let us x ∈ [0, 1], and suppose we have access to the additional information, for

1 ≤ i ≤ N Y i = x 0 i if L i = 1, * if L i = 0, (24)
where

L i i.i.d.
∼ Ber( ) and * is a symbol that does not belong to R. The posterior distribution of X is now

P (X|Y, Y ) = 1 Z N,   i|Y i = * 1(x i = Y i )     i|Y i = * P X (x i )   e H N (X) ,
where Z N, is the appropriate normalization constant. For X = (x 1 , . . . , x N ) ∈ R N we will use the notation

X = (L 1 x 0 1 + (1 -L 1 )x 1 , . . . , L N x 0 N + (1 -L N )x N ) . ( 25
)
X is thus obtained by replacing the coordinates of X that are revealed by Y by their revealed values. The notation X will allow us to obtain a convenient expression for the free energy of the perturbed model X) .

F N, = 1 N E log Z N, = 1 N E log X∈S N P X (X)e H N (
The next lemma shows that the perturbation does not change the free energy up to the order of . Recall that we supposed the support S of P X to be nite, so we can nd a constant K such that S ⊂ [-K, K].

Lemma 1. For all n ≥ 1 and all , ∈ [0, 1], we have

|F N, -F N, | ≤ K 2p ∆ | -|.
Lemma 1 follows from a direct adaptation of Proposition 23 from [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] to the tensor case. Consequently, if we suppose ∼ U([0, 1]) and de ne N = N -1/2 and L i i.i.d.

∼ Ber( N ), independently of everything else, we have

|F N -E [F N, N ]| ----→ N →∞ 0 , ( 26
)
where E denotes the expectation with respect to only. It remains therefore to compute the limit of the free energy under a small perturbation. As shown in [START_REF] Montanari | Estimating random variables from random sparse observations[END_REF], the perturbation [START_REF] Richard | A statistical model for tensor PCA[END_REF] forces the correlations to vanish asymptotically.

Lemma 2 (Lemma 3.1 from [START_REF] Montanari | Estimating random variables from random sparse observations[END_REF]).

E   1 N 2 1≤i,j≤N I(x 0 i ; x 0 j | Y, Y )   ≤ 2H(P X ) √ N .
Let us write • the expectation with respect to P (X = • | Y, Y ), and let X (1) , X (2) be two independents samples from P (X = • | Y, Y ), independently of everything else. We de ne Q = X (1) • X (2) . Notice that Q is a non-negative random variable. As a consequence of Lemma 2, the overlaps under the posterior distribution concentrates around Q:

Lemma 3. E X (1) • X (2) -Q 2 ----→ N →∞ 0 and E X (1) • X 0 -Q 2 ----→ N →∞ 0 , ( 27
)
where E denotes the expectation with respect all random variables.

Lemma 3 follows from the arguments of section 4.4 from [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF].

The arguments presented in this section are robust and apply to a large class of Hamiltonians. In particular, we will be able to apply in the sequel Lemmas 1 and 3 to other Hamiltonians and posterior distributions (and corresponding free energies).

Guerra's interpolation scheme

The lower bound is obtained by extending the bound derived for p = 2 in [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF], using a Guerra-type interpolation [START_REF] Guerra | Broken replica symmetry bounds in the mean eld spin glass model[END_REF] as was already done for tensors by Korada and Macris in [START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF] (who consider tensors in the special case of Rademacher P X ).

Lemma 4.

lim inf

N →∞ F N ≥ sup m≥0 φ RS (m) .
Proof. We use a Guerra-type interpolation [START_REF] Guerra | Broken replica symmetry bounds in the mean eld spin glass model[END_REF]: Let 0 ≤ t ≤ 1 and m ∈ R + . We suppose to observe Y and Ỹ

given by

       Y i 1 ,...,ip = t(p -1)! N (p-1)/2 x 0 i 1 . . . x 0 ip + V i 1 ,...,ip for 1 ≤ i 1 < • • • < i p ≤ N Ỹj = (1 -t)m p-1 x 0 j + Ṽj for 1 ≤ j ≤ N
where the variables V i 1 ,...,ip and Ṽj are i.i.d. N (0, ∆) random variables. We de ne the interpolating Hamiltonian

H N,t (X) = ∆ -1 i 1 <•••<ip t(p -1)! N (p-1)/2 Y i 1 ,...,ip x i 1 . . . x ip - t(p -1)! 2N p-1 (x i 1 . . . x ip ) 2 + ∆ -1 N j=1 (1 -t)m p-1 Ỹj x j - 1 2 (1 -t)m p-1 x 2 j .
Then, the posterior distribution of X 0 given Y and Ỹ reads

P (X 0 = X|Y, Ỹ ) = 1 Z N,t P X (X) exp(H N,t (X)) , (28)
where Z N,t is the appropriate normalization. Let ψ

N (t) = 1 N E[log Z N,t ] be the corresponding free energy. Notice that ψ N (1) = F N , ψ N (0) = φ RS (m) -(1-p)m p 2∆p .
Let • t denote the expectation with respect to the posterior (28) and let X be a sampled from [START_REF] Zdeborová | Statistical physics of inference: Thresholds and algorithms[END_REF], independently of everything else.

Using Gaussian integration by parts and the Nishimori identity of Proposition 1 one can show (see [START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF][START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF]) that for all 0 ≤ t ≤ 1

ψ N (t) = 1 2∆p E X • X 0 p -pm p-1 X • X 0 t + o N (1)
.

By convexity of the function a → a p on R + we have, for all a, b ≥ 0: a p -pb p-1 a ≥ (1 -p)b p . We would like to use this inequality with a = X • X 0 and b = m to obtain that ψ N (t) ≥ (1-p)m p 2∆p . This would conclude the proof of the lower bound because lim inf

N →∞ F N = lim inf N →∞ ψ N (1) = lim inf N →∞ ψ N (0) + 1 0 ψ N (t)dt ≥ φ RS (m) .
However, we do not know that X • X 0 ≥ 0 almost surely. To bypass this issue we can add, as in sec. 5.1, a small perturbation (24) that forces X • X 0 concentrates around a non-negative value (Lemma 3), without a ecting the "interpolating free energy" ψ N (t) in the N → ∞ limit, see [START_REF] Talagrand | Mean eld models for spin glasses: Volume I: Basic examples[END_REF]. The arguments are the same than in sec. 5.1, so we omit the details and the rewriting of the previous calculations with the perturbation term. This concludes the proof.

Proving the upper-bound: Aizenman-Sims-Starr scheme

We are now going to show how the arguments of [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF] for the upper bound -using cavity computations with an Aizenman-Sims-Starr approach [START_REF] Michael Aizenman | Extended variational principle for the Sherrington-Kirkpatrick spin-glass model[END_REF]-can be extended to the tensor case.

Lemma 5.

lim sup

N →∞ F N ≤ sup m≥0 φ RS (m) .
Proof. We are going to compare the system with N variables to the system with N + 1 variables. De ne

A N = E[log Z N +1 ] -E[log Z N ]. Consequently, F N = 1 N N -1 k=0
A k and lim sup F N ≤ lim sup A N . We are thus going to upper-bound A N . Let X ∈ S N be the N -rst variables and σ ∈ S the (N + 1) th variable. We decompose H N +1 (X, σ) = H N (X) + σz(X) + σ 2 s(X) where

H N (X) = i 1 <•••<ip ∆ -1 (p -1)! (N + 1) (p-1)/2 Y i 1 ...ip x i 1 . . . x ip - ∆ -1 (p -1)! 2(N + 1) p-1 (x i 1 . . . x ip ) 2 , z(X) = ∆ -1 i 1 <•••<i p-1 ≤n (p -1)! (N + 1) (p-1)/2 Y i 1 ...i p-1 ,n+1 x i 1 . . . x i p-1 , s(X) = -∆ -1 i 1 <•••<i p-1 ≤n (p -1)! 2(N + 1) p-1 (x i 1 . . . x i p-1 ) 2 .
One can also decompose H N (X) = H N (X) + y(X) in law, where

y(X) = ∆ -1 i 1 <•••<ip (p -1)! p -1 N p + r n 1/2 V i 1 ...ip x i 1 . . . x ip + (p -1)! p -1 N p + r n x 0 i 1 . . . x 0 ip x i 1 . . . x ip - 1 2 (x i 1 . . . x ip ) 2 .
In the above de nition, the V are i.i.d. N (0, ∆) random variables, independent of everything else, and r n = o(N -p ). If we denote by • the Gibbs measure on S N corresponding to the Hamiltonian log P X + H N we can rewrite

A N = E log σ∈S P X (σ)e σz(X)+σ 2 s(X) -E log e y(X) , ( 29
)
where X is a sample from • , independently of everything else. A N is thus a di erence of two terms that will correspond exactly to the terms of [START_REF] Panchenko | The Sherrington-Kirkpatrick model[END_REF]. As in sec. 5.1, we can show that under a small perturbation of the system, the overlap X • X 0 with the planted con guration concentrates around a non-negative value Q . This leads to simpli cations in (29):

lim sup N →∞ A N ≤ lim sup N →∞ E[φ RS (Q )] ≤ F RS . (30)
For a precise derivation of (30), the reader is invited to report to the matrix case (see [START_REF] Lelarge | Fundamental limits of symmetric low-rank matrix estimation[END_REF], sec. 4.6), since there is no major di erence with the tensor case on this point. The arguments presented there are commonly used in the study of spin glasses and are the analog of cavity computations in the SK model developed in [START_REF] Talagrand | Mean eld models for spin glasses: Volume I: Basic examples[END_REF], sec. 1.5. This concludes the proof.

6 Examples of phase transitions We used the state evolution eqs. [START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF][START_REF] Krzakala | Mutual information in rank-one matrix estimation[END_REF], and the free energy [START_REF] Lesieur | Phase transitions in sparse PCA[END_REF], to compute the values of the thresholds ∆ c , ∆ IT and ∆ Alg for several examples of the prior distributions: Gaussian (spherical spins), P X (x) = N (µ, 1); Rademacher (Ising spins), P X (x) = 1 2 [δ(x -1) + δ(x + 1)]; Bernoulli (sub-tensor localization), P X (x) = ρδ(x -1) + (1 -ρ)δ(x); and clustering (tensor stochastic block model),

P X (x) = 1 r r k=1 δ(x -e k ),
where e k ∈ R r is a vector with a 1 at coordinate k and 0 elsewhere. Examples of values of the thresholds for the above priors are given in Table 1. For the zero mean Gaussian and the Rademacher prior our results for ∆ IT indeed agree with those presented in [START_REF] Babu | Exact solution of the gauge symmetric p-spin glass model on a complete graph[END_REF][START_REF] Perry | Statistical limits of spiked tensor models[END_REF]. Central and right part of Fig. 1 present the thresholds for the Gaussian and Bernoulli prior as a function of the mean µ and density ρ, respectively. Left part of Fig. 1 illustrates that indeed the xed points of the state evolution agree with the xed points of the AMP algorithm. For the Bernoulli case the rescaling in power of ρ is for convenience to present quantities of order one, we did not check if it describes the large p limit.

∆ IT p log(p) ∆ Alg ∆ IT ∆ Alg ∆ IT ρ -p ∆ Alg ρ -2p+2 ∆ IT ∆ Alg ∆ Alg r 2p-2 p-1 2 2 log 2 1 1 1 - - 1

Results for Gaussian prior

In this section we detail the analysis of the state evolution for rank r = 1 Gaussian prior of mean µ and variance 1.

P Gauss X = N (µ, 1) . (31)
Using ( 12) one gets for the SE equation

M t+1 = ∆µ 2 + (M t ) p-1 (1 + µ 2 ) ∆ + (M t ) p-1 , ( 32
)
where M is a scalar, and ∆ is the inverse Fisher information of the output channel. It turns out that as soon as p ≥ 3 the SE equation exhibits multiple stable xed points.

For the zero mean µ = 0 case one gets

M t+1 = (M t ) p-1 ∆ + (M t ) p-1 . (33)
Here the xed point M = 0 is stable whatever the noise ∆ > 0 and therefore AMP will not achieve performance better than random guessing for any ∆ > 0. Ref. [START_REF] Richard | A statistical model for tensor PCA[END_REF] studies the scaling of ∆ with N for which AMP and other algorithms succeed.

For positive mean µ > 0, however, the AMP algorithm is able to recover the signal for values of ∆ < ∆ Alg with

∆ Alg (µ) = x p-2 Alg (1 + x Alg ) p-1 , ∆ Dyn (µ) = x p-2 Dyn (1 + x Dyn ) p-1 , (34)
x

Alg (µ) = p -2 + 2µ 2 -(p -2) 2 -4µ 2 (p -1) 2(1 + µ 2 ) , (35)
x

Dyn (µ) = p -2 + 2µ 2 + (p -2) 2 -4µ 2 (p -1) 2(1 + µ 2 ) , (36)
where we de ned a new threshold ∆ Dyn as the smallest such that for ∆ > ∆ Dyn the state evolution has a unique xed point. We know of no analytical formula for ∆ IT and for Figure 1 we computed it numerically. The tri-critical point where all these curve meet is located at

µ Tri = p -2 2 √ p -1 . (37)
Using the above expressions we derive that

∆ Dyn (µ = 0) = 1 p -2 p -2 p -1 p-1 ∼ p→∞ 1 ep , (38)
∆ Alg (µ) ∼ µ→0 µ 2 p -2 p-2 . ( 39
)
We can also compute the limit of the ∆ IT (µ = 0, p) as p → ∞ and get

∆ IT (µ = 0, p) ∼ p→∞ 1 p log(p) . ( 40
)
This scaling agrees with the large p behavior derived in [START_REF] Richard | A statistical model for tensor PCA[END_REF] and [START_REF] Perry | Statistical limits of spiked tensor models[END_REF].

Results for clustering prior

An interesting example of the prior for rank r tensor estimation is

P Clusters X (x) = 1 r 1≤k≤r δ(x -e k ) . (41)
This describes a model of r non-overlapping clusters. Due to the channel universality, this prior also describes the stochastic block model on dense hyper-graphs as considered for sparse hyper-graph in e.g. [START_REF] Chiara Angelini | Spectral detection on sparse hypergraphs[END_REF]. This model was considered in detail for p = 2 in [START_REF] Thibault Lesieur | Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications[END_REF].

The above clustering prior has non-zero mean, and it also exhibits the transition ∆ c from a phase where recovery of clusters better than chance is not possible, to a phase where it is.

To analyze the SE equations we rst notice that the stable xed point will be of the form

M = bI r r + (1 -b)J r r 2 ∈ R r×r , b ∈ [0; 1] , (42)
where I r is the identity matrix and J r is a matrix lled with ones. b = 0 means that the estimate of the marginals does not carry any information. b = 1 means perfect reconstruction. The state evolution now becomes

b t+1 = M r   r b t r + 1-b t r 2 p-1 -1-b t r 2 p-1 ∆    , (43)
where M r is a function that was de ned and studied in [START_REF] Lesieur | MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel[END_REF]. Its Taylor expansion is

m is a xed point of (43) when m = m(x) and ∆ = ∆(x). Rather than nding the xed point iteratively, the above equations allow us to draw all the xed point of (43), be it stable or unstable We have that m(x) is a stable xed point of (43) if and only if

∂∆(x) ∂x < 0 . ( 49
)
The next question is whether there is a rst or second order phase transition at ∆ c . To answer this, one needs to analyze whether the xed point close to b = 0 is stable or unstable. For this we to compute ∂∆(x) ∂x at x = 0 to get using (44) that

∂∆(x) ∂x = p -1 2r 2p (-2p -r + pr) . (50)
Therefore if -2p -r + pr > 0 there will be no stable xed point close to b = 0 and the system must have a rst order phase transition (discontinuity in the MSE AMP ) at ∆ c = ∆ Alg . For two clusters r = 2, there is a second order phase transition at ∆ c for all p ≥ 2. However, analyzing the state evolution numerically we observed that for p ≥ 5 there is a discontinuity later at some ∆ Alg < ∆ c . For three and more clusters r ≥ 3 we always have ∆ Alg = ∆ c , and for -2p-r +pr ≤ 0 we have not detected any other discontinuities. Values of ∆ IT for three clusters and some values of p are given in Table 1.

Figure 1 :

 1 Figure 1: Left panel: Comparison between the AMP xed point reached from uninformative (marked with crosses) or informative (i.e. strongly correlated with the ground truth, marked with pluses) initialization and the xed point of the SE equations (stable xed point in blue, unstable in red). The data are for the Gaussian prior with mean µ = 0.2, unit variance, p = 3, r = 1. The AMP runs are done on a system of size N = 1000. Central panel: Phase diagram for the order p = 3 tensor factorization, rank r = 1, Gaussian prior of mean µ (x-axes) and unit variance. In the green-shaded zone AMP matches the information-theoretically optimal performance, MMSE = MSE AMP . In the orange-shaded zone MMSE < MSE AMP . The tri-critical point is located at µ Tri = (p -2)/(2 √ p -1) and ∆ Tri = x p-2 Tri /(1 + x Tri ) p-1 where x Tri = (p -2)(3p -4)/p 2 . Right panel: Phase diagram for the order p = 3 tensor factorization, rank r = 1, the Bernoulli prior as a function of ρ and ∆/ρ 4 . The tri-critical point is located at ρ Tri = 0.178 and ∆ Tri /ρ 4 = 2.60. As ρ → 0 we observed ∆ Alg /ρ 4 → 2e. Compare to Fig. 5 in [17] where the same phase diagram is presented for the matrix factorization p = 2 case.

M r (x) = x r 2 + x 2 r -4 2r 4 +

 24 O x 3 . (44)We further notice that b = 0 is always a xed point of (43). By expanding (43) to rst order one getsb t+1 = b t p -1 ∆r 2p-2 + O b t 2 . (45)This xed point therefore becomes unstable when∆ < ∆ c ≡ p -1 r 2p-2 .(46)By analyzing eq. (43) further we can prove that ∀x ∈ R + m(x) = M r (x)

Table 1 :

 1 Examples of the information-theoretic ∆ IT and algorithmic ∆ Alg thresholds for order-p tensor decomposition for di erent priors on the factors. For the Gaussian case ∆ IT p log(p) converges to 1 at large p.

	1

Acknowledgment

This work has been supported by the ERC under the European Union's FP7 Grant Agreement 307087-SPARCS.