تقرير
Tensor cumulants for statistical inference on invariant distributions
| العنوان: | Tensor cumulants for statistical inference on invariant distributions |
|---|---|
| المؤلفون: | Kunisky, Dmitriy, Moore, Cristopher, Wein, Alexander S. |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics Statistics |
| مصطلحات موضوعية: | Mathematics - Statistics Theory, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Mathematics - Probability, Statistics - Machine Learning |
| الوصف: | Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretically possible, but (conjecturally) computationally intractable. A canonical such problem is Tensor PCA, where we observe a tensor $Y$ consisting of a rank-one signal plus Gaussian noise. Multiple lines of work suggest that Tensor PCA becomes computationally hard at a critical value of the signal's magnitude. In particular, below this transition, no low-degree polynomial algorithm can detect the signal with high probability; conversely, various spectral algorithms are known to succeed above this transition. We unify and extend this work by considering tensor networks, orthogonally invariant polynomials where multiple copies of $Y$ are "contracted" to produce scalars, vectors, matrices, or other tensors. We define a new set of objects, tensor cumulants, which provide an explicit, near-orthogonal basis for invariant polynomials of a given degree. This basis lets us unify and strengthen previous results on low-degree hardness, giving a combinatorial explanation of the hardness transition and of a continuum of subexponential-time algorithms that work below it, and proving tight lower bounds against low-degree polynomials for recovering rather than just detecting the signal. It also lets us analyze a new problem of distinguishing between different tensor ensembles, such as Wigner and Wishart tensors, establishing a sharp computational threshold and giving evidence of a new statistical-computational gap in the Central Limit Theorem for random tensors. Finally, we believe these cumulants are valuable mathematical objects in their own right: they generalize the free cumulants of free probability theory from matrices to tensors, and share many of their properties, including additivity under additive free convolution. Comment: 72 pages, 12 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2404.18735 |
| رقم الأكسشن: | edsarx.2404.18735 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |