|
|
|
Program - week 1
>> COURSES
Gérard Ben Arous - Random Tensors: from Spin Glasses to Data Science
I will cover recent progress on the question of high dimensional Tensor PCA, i.e. estimating a finite rank tensor in high dimensions from a noisy sample. This will be based on recent work with Reza Gheissari (Northwestern), Jiaoyang Huang (Wharton, U-Penn), Aukosh Jagannath (Waterloo), Cedric Gerbelot (Courant, NYU), Vanessa Piccolo (ENS Lyon). I will start with the single spike case, i.e. when the rank is one. I will cover quickly the three natural questions and their answers: the first one is information theoretic (when is the estimation problem solvable), the next one is statistical (when is it solvable with a given statistical procedure, say Maximum Likelihood Estimation) and the last one is algorithmic (when are the natural optimization algorithms working to solve the statistical problem). Each of these questions induces a priori different thresholds in terms of the necessary amount of data. When we use the simplest statistical method, i.e. MLE, a very natural link with statistical physics of disordered media emerges, i.e. with spherical spin glasses. Indeed the likelihood function is very naturally related to the Hamiltonian of a spherical spin glass. I will survey quickly this link and what it gives us, in particular for the topological information about the optimization landscape using known results from the world of spherical spin glasses. I will then explore the recent results about the dynamics of optimization in this MLE landscape, with various natural algorithms, insisting on the most natural one, i.e. SGD (Stochastic Gradient Descent). If time permits, I will show how this model has served as a paradigm for many other high-dimensional estimation problems, and how it helped introduce the notion of "information exponent" for general “single-index” models. The next step will be to look at the much more complex question of multi-spiked tensor estimation, i.e. when the rank of the signal is greater than 1. I will start with recent results by Vanessa Piccolo on the topological complexity. And then cover the very recent work with Vanessa Piccolo and Cedric Gerbelot on the optimization dynamics for these multi-spiked Tensor PCA questions.
Matthias Christandl - The tensor as an informational resource
A tensor is a multidimensional array of numbers that can be used to store data, encode a computational relation and represent quantum entanglement. In this sense a tensor can be viewed as valuable resource whose transformation can lead to an understanding of structure in data, computational complexity and quantum information. In order to facilitate the understanding of this resource, we propose a family of information-theoretically constructed preorders on tensors, which can be used to compare tensors with each other and to assess the existence of transformations between them. The construction places copies of a given tensor at the edges of a hypergraph and allows transformations at the vertices. A preorder is then induced by the transformations possible in a given growing sequence of hypergraphs. The new family of preorders generalises the asymptotic restriction preorder which Strassen defined in order to study the computational complexity of matrix multiplication. We derive general properties of the preorders and their associated asymptotic notions of tensor rank and view recent results on tensor rank non-additivity, tensor networks and algebraic complexity in this unifying frame. We hope that this work will provide a useful vantage point for exploring tensors in applied mathematics, physics and computer science, but also from a purely mathematical point of view.
The lecture notes for this course are this review paper.
Sabine Harribey - An introduction to tensor models: from random geometry to melonic CFTs
Tensor models are particularly interesting due to their melonic large-N limit which is richer than the large-N limit of vector models but simpler than the planar limit of matrix models. Tensor models were first introduced in zero dimension in the context of random geometry and quantum gravity. They were then extended to quantum mechanical models in one dimension as an alternative to the Sachdev-Ye-Kitaev model without disorder. Finally, they were generalised in higher dimensions as toy models for strongly-coupled QFTs. In this context, they give rise in the infrared to a new kind of conformal field theories analytically accessible, called melonic CFTs. In these lectures, after reviewing the large-N expansion of vector and matrix models, I will introduce complex colored tensor models and derive their melonic large-N limit. The second part of the lectures will focus on the bosonic O(N)3 model first studied in arXiv:1512.06718. We will derive its large-N limit and study criticality of the Schwinger-Dyson equation in zero dimension. At the end of the lectures, I will briefly present the generalisation of this model in higher dimensions and how it leads to a melonic CFT in the infrared.
Ion Nechita - Tensor freeness and applications to quantum information theory
This lecture series presents a novel generalization of Voiculescu's free independence concept to the tensor setting. Our approach is designed for random matrix models that exhibit independence under conjugation by tensor products of Haar-distributed, independent, random unitary matrices. We introduce the concept of "tensor freeness," which describes the limiting behavior of independent, locally unitarily invariant random matrix families. Our theory is built upon a new moment/tensor free cumulant formula, utilizing the combinatorics of permutation tuples. We demonstrate that, given the existence of a limit "tensor distribution" described by permutation tuples, an independent family of locally unitarily invariant random matrices exhibits tensor-freeness in the large dimension limit. The theory is developed with a focus on applications to quantum information theory, where local unitary invariance is prevalent. Additionally, we propose a tensor-free version of the central limit theorem, extending and encompassing several previous results. This work is conducted jointly with Sang-Jun Park.
David Pérez-García - Tensor Networks: a mathematical tool to understand exotic quantum phases of matter
Tensor networks are a mathematical structure based on quantum information ideas which capture the low energy sector of many body quantum systems. They have been used as an important mathematical tool to study and characterize exotic quantum phases of matter. In this lecture series, I will present some of the main results and ideas in this direction. Content: 1.- Diagramatic notation of tensor networks. Examples. 2.- Tensor Networks as ground states. 3.- The fundamental theorem. 4.- Symmetry protected topological order. 5.- Intrinsic topological order.
Main references: JI Cirac, D Perez-Garcia, N Schuch, F Verstraete, Matrix product states and projected entangled pair states: Concepts, symmetries, theorems, Reviews of Modern Physics 93 (4), 045003 (2021); arXiv:2011.12127. A. Molnar et al., Matrix product operator algebras I: representations of weak Hopf algebras and projected entangled pair states, arXiv:2204.05940.
Juan Luis Araujo Abranches - Matrix Models for Matter on Random Geometries with Causal Constraints
In this talk, I will introduce a multi-matrix model aiming to understand the properties of matter coupled to causal random geometries. We used a dually-weighted matrix model corresponding to two-dimensional Causal Dynamical Triangulations coupled to the Ising model. Among the novel results are: (i) an exact formula for the Gaussian averages of characters of the square of a Hermitian matrix for a given representation; (ii) an explicit large N expression for the eigenvalues of the matrix enforcing the causal constraint; and (iii) the solution of the unitary integral of fourth order monomials using Weingarten calculus. I will conclude the talk by presenting a multi-matrix field theory inspired by the Grosse-Wulkenhaar model. The techniques developed for this multi-matrix field theory model will pave the way for forming matter models on causal dynamical geometries generated from tensor field theories and potentially provide an escape route from the branched polymer phase.
Slides available here.
Pierre Botteron - Nonlocal boxes seen as tensors and used to determine if a physical theory is realistic or not
Nonlocal boxes are 2x2x2x2 tensors that generalize the notion of quantum correlations. Some of these tensors violate fundamental principles, leading to the strong conclusion that any physical theory involving these tensors is interpreted as unrealistic. We know from experiments that Quantum Mechanics (QM) is a realistic theory, but we do not know yet if it is the more general theory that accurately describes the world. This raises the following question: if a tensor comes from a more general theory than QM, does it violate some fundamental principle? If so, it would mean that QM is the most general theory describing correlations between distant parties. To this end, we show that some beyond-than-quantum tensors violate the principle of communication complexity and thus are physically unrealistic.
References: [1] Physical Review Letters, 132, 070201 (2024) [ https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.132.070201 ]. [2] Quantum 8, 1402 (2024) [ https://quantum-journal.org/papers/q-2024-07-10-1402/ ]. [3] arXiv:2406.02199 [quant-ph] (2024) [ https://arxiv.org/abs/2406.02199 ].
Slides available here.
Issa-Mbenard Dabo - Traffic Distribution of Profiled Non-Linear Matrices
This paper addresses the macroscopic asymptotics of large random matrices of the form Y = 1 / N21/2 h[{W X / N01/2}], where W and X are random rectangular matrices with independent entries and h is a function applied entry-wise. We allow the variance of the entries of the W and X to vary from entry to entry, extending the Pennington - Worah matrices framework to the case of variance profiled matrices. This matrix can be interpreted as a one-layer neural network whose performance is related to its spectrum. We compute the traffic distribution of this ensemble, which enables us to derive an asymptotic traffic equivalent of the non-linear matrix. The approach used to obtain this traffic equivalent provides a new explanation of the linear-plus-chaos phenomenon for Pennington-Worah matrices.
Slides available here.
Marco Fanizza - Learning finitely correlated states: stability of the spectral reconstruction
Matrix product operators allow efficient representations (equivalently, realizations) of states on a 1D lattice. We consider the task of learning a realization of minimal dimension from copies of an unknown state, such that the resulting operator is close to the density matrix in trace norm. For finitely correlated, translation-invariant states on an infinite spin-chain, a realization of minimal dimension can be exactly recovered via linear algebra operations from the knowledge of a finite size marginal, whose size is bounded by a function of the realization dimension. We thus consider an algorithm that, given approximate knowledge of a marginal of large enough size, estimates a candidate realization. For any size t, a matrix product operator can be reconstructed from the candidate realization, to estimate the corresponding marginal of the unknown state. We establish a bound on the trace norm error of this estimate as a function of t, local spin dimension, representation dimension and spectral properties of a certain map constructed from the state. This bound allows us to establish an O(t2) upper bound on the sample complexity of the learning task, and polynomial dependence on the other parameters above. The computational complexity of obtaining the candidate representation is also polynomial in t. In the error analysis, the theory of operator systems plays a central role.
A refined error bound can be proven for C*-finitely correlated states, which have an operational interpretation in terms of sequential quantum channels applied to the memory system. We can also obtain an analogous error bound for a class of non-translation invariant matrix product density operators on a finite chain, reconstructible from local marginals. In this case, a linear number of marginals must be estimated, obtaining a sample complexity of Õ(t3). The learning algorithm also works for states that are only close to a finitely correlated state, with the potential of providing competitive algorithms for other interesting families of states.
Based on: Fanizza, M., Galke, N., Lumbreras, J., Rouzé, C., & Winter, A. Learning finitely correlated states: stability of the spectral reconstruction. arXiv:2312.07516.
Slides available here.
Marta Florido Llinas - From regular languages to quantum states
In this talk, I will introduce regular language quantum states (RLS), a physically relevant family of quantum many-body states based on the well-developed theory of regular languages from computer science. I will explain how this connection can be leveraged to develop a theoretical framework for RLS in terms of matrix product states (MPS), enabling us to address key challenges, such as local-unitary equivalence, that conventional MPS theory cannot handle. I will also highlight some applications and potential generalizations (https://arxiv.org/abs/2407.17641).
Slides available here.
Guglielmo Lami - Anticoncentration in Random Tensor Network states
We study the inverse participation ratio (IPR) of random Matrix Product States in the computational basis. We obtain analytical expressions for the IPR at any order for both open and closed boundary conditions. We also find the leading order of the associated probability distribution (aka collision or overlaps probability distribution) in a certain scaling limit. We moreover obtain numerical results for the frame potential of MPS and for the 2-dimensional case, by means of random Projected Entangled Plaquette States (PEPS).
Hugo Lebeau - A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation
This work presents a comprehensive understanding of the estimation of a planted low-rank signal from a general spiked tensor model near the computational threshold. Relying on standard tools from the theory of large random matrices, we characterize the large-dimensional spectral behavior of the unfoldings of the data tensor and exhibit relevant signal-to-noise ratios governing the detectability of the principal directions of the signal. These results allow to accurately predict the reconstruction performance of truncated multilinear SVD (MLSVD) in the non-trivial regime. This is particularly important since it serves as an initialization of the higher-order orthogonal iteration (HOOI) scheme, whose convergence to the best low-multilinear-rank approximation depends entirely on its initialization. We give a sufficient condition for the convergence of HOOI and show that the number of iterations before convergence tends to 1 in the large-dimensional limit.
Slides available here.
Thomas Muller - Duality and double scaling limit of random tensor models
Random matrix models can be used to generate maps indexed by their genus g. A generalization of such models is given by rank d random tensor models, where the generated graphs are (d+1)-edge coloured graphs (or equivalently d-stranded graphs) indexed by Gurau’s degree. In this talk, I will present two aspects of such tensor models. First, I will discuss the double scaling limit of a tensor model whose interaction possesses the topology of a prism. In this limit, achieved by tuning the coupling constant of the interaction to its critical value and the size of the tensors to infinity, a richer family of graphs contributes compared to the one in the simple large N limit. In a second part, I will present a duality that links tensor models with O(N) symmetry to dual models with Sp(N) symmetry. Such duality holds graph by graph in perturbation theory.
Slides available here.
Sang-Jun Park - Tensor-freeness and central limit theorem
Voiculescu's notion of asymptotic free independence applies to a wide range of random matrices, including those that are independent and unitary invariant. In this talk, we generalize this notion by considering random matrices with a tensor product structure that are invariant under the action of local-unitaries. We show that, given the existence of limit 'tensor-moments' described by tuples of permutations, an independent family of local-unitary invariant random matrices satisfies a new kind of freeness in the limit, which we will call 'tensor-freeness'. This can be defined via vanishing mixed 'tensor-free cumulants', allowing the joint moments of tensor-free elements to be described in terms of that of individual elements. Additionally, we propose a tensor-free version of the central limit theorem, which extends and recovers the recent results on central limit theorem for tensor products of free variables. This is joint work with Ion Nechita.
Slides available here.
Vanessa Piccolo - Dynamics of optimization in high dimensions for multi-spiked tensor PCA
We will study the high-dimensional statistical problem of multi-spiked tensor PCA, where the goal is to infer a finite number of unknown, orthogonal signal vectors from noisy observations of a p-tensor. I will present our recent results on the sample complexity required for stochastic gradient descent to efficiently recover the spikes from natural initializations. We will distinguish between three types of recovery: exact recovery of each spike, recovery of a permutation of all spikes, and recovery of the correct subspace spanned by the unknown signal vectors. This work is based on joint work with Gérard Ben Arous (NYU) and Cédric Gerbelot (NYU).
Slides available here.
Anas Rahman - Tensor Estimation at Growing Rank
With Jean Barbier and Justin Ko, we recently showed that the mutual information between an NxM signal matrix X and output Y = XX* + Z, with Gaussian noise Z and when M = o(N^{1/10}), is given by the same Parisi formula as when M = 1. We believe that our methods should extend to the general even-order tensor case (where we've thus far looked at the order 2 tensor XX*). However, there are subtle challenges in making this extension that could benefit from eyes in the random tensor community. Moreover, it would be good to get ideas on whether such results should also hold for all M = O(N).
Slides available here.
Naoki Sasakura - Signed eigenvalue distributions of complex random tensors and geometric measure of entanglement of multipartite states
Eigenvalue/vector distributions of random tensors can systematically be computed as partition functions of quantum field theories of bosons and fermions. In particular, signed distributions, which are the distributions with sign factors coming from Hessian matrices, are expressed as partition functions of four-fermi theories, which are in principle exactly computable. Though the distributions and the signed distributions are different, they have intimate relations in the large-N limit and in particular their edges coincide. In this talk, we obtain the exact closed-form expressions of the signed eigenvalue/vector distributions of complex tensors with symmetric or independent indices. As applications we determine the asymptotic forms of the geometric measure of entanglement of multipartite states, which agree with the previous numerical study by Fitter, Lancien, and Nechita. We also discuss some open questions.
Slides available here.
Reiko Toriumi - Counting of U(N)⊗p ⊗ O(N)⊗q invariants.
In this work [1], we undertake a counting problem motivated by random tensor models, using permutation group techniques. Our method unveils novel enumerative constructions and correspondences, and may enrich different domains such as topology, combinatorics and computer science. This work extended previous works [2] and [3], and in particular, looked at the counting formulas for U(N)⊗p ⊗ O(N)⊗q invariants.
By providing a systematic way to count tensor invariants, we unveiled a new correspondence between the number of multi-orientable-model observables and topological quantum field theory (TQFT) on particular cellular complexes. We wish to highlight our newly discovered integer sequences added to OEIS. Références: [1] R. Avohou, J. Ben Geloun, R. Toriumi, Eur. Phys. J. C 84 (2024) 8, 839 [2] J. Ben Geloun, S. Ramgoolam, ``Counting Tensor Model Observables and Branched Covers of the 2-Sphere", Ann. Inst. H. Poincare D Comb. Phys. Interact. 1 (2014) no.1, 77-138 [3] R. Avohou, J. Ben Geloun, N. Dub, ``On the counting of O(N) tensor invariants”, Theor. Math. Phys. 24 (2020), no.4, 821–878 Slides available here.
|
| Online user: 2 | Privacy |
|
