分析大型随机矩阵的浓度是多种领域的常见任务。给定独立的随机变量，许多工具可用于分析随机矩阵，其条目在变量中是线性的，例如基质 - 伯恩斯坦不平等。但是，在许多应用中，我们需要分析其条目是变量中多项式的随机矩阵。这些自然出现在光谱算法的分析中，例如霍普金斯等人。 [Stoc 2016]，Moitra-Wein [Stoc 2019]；并根据正方形层次结构的总和（例如Barak等。 [FOCS 2016]，Jones等。 [焦点2021]。在这项工作中，我们基于Paulin-Mackey-Tropp（概率Annals of Poylibity of Poyliby of 2016]，我们提出了一个通用框架来获得此类界限。 Efron-Stein不等式通过另一个简单（但仍然是随机）矩阵的范围来界定随机矩阵的规范，我们将其视为通过“区分”起始矩阵而引起的。通过递归区分，我们的框架减少了分析更简单的矩阵的主要任务。对于Rademacher变量，这些简单的矩阵实际上是确定性的，因此，分析它们要容易得多。对于一般的非拉多巴纳变量，任务减少到标量浓度，这要容易得多。此外，在多项式矩阵的设置中，我们的结果推广了Paulin-Mackey-Tropp的工作。使用我们的基本框架，我们在文献中恢复了简单的“张量网络”和“密集图矩阵”的已知界限。使用我们的一般框架，我们得出了“稀疏图矩阵”的边界，琼斯等人最近才获得。 [焦点2021]使用痕量功率方法的非平地应用，并且是其工作中的核心组成部分。我们希望我们的框架对涉及非线性随机矩阵浓度现象的其他应用有帮助。

我们开发了一种高效的随机块模型中的弱恢复算法。该算法与随机块模型的Vanilla版本的最佳已知算法的统计保证匹配。从这个意义上讲，我们的结果表明，随机块模型没有稳健性。我们的工作受到最近的银行，Mohanty和Raghavendra（SODA 2021）的工作，为相应的区别问题提供了高效的算法。我们的算法及其分析显着脱离了以前的恢复。关键挑战是我们算法的特殊优化景观：种植的分区可能远非最佳意义，即完全不相关的解决方案可以实现相同的客观值。这种现象与PCA的BBP相转变的推出效应有关。据我们所知，我们的算法是第一个在非渐近设置中存在这种推出效果的鲁棒恢复。我们的算法是基于凸优化的框架的实例化（与平方和不同的不同），这对于其他鲁棒矩阵估计问题可能是有用的。我们的分析的副产物是一种通用技术，其提高了任意强大的弱恢复算法的成功（输入的随机性）从恒定（或缓慢消失）概率以指数高概率。

给定尺寸$ d $中的独立标准高斯点$ v_1，\ ldots，v_n $，对于$（n，d）$的值（n，d）$的值很高，概率很高，同时通过所有要点？将椭圆形拟合到随机点的基本问题与低级别矩阵分解，独立的组件分析和主成分分析有连接。基于有力的数值证据，桑德森，帕里洛和威尔斯基[Proc。关于决策和控制会议，第6031-6036页，2013年]猜想，椭圆形拟合问题的问题从可行的到不可行的$ n $增加，并在$ n \ sim d^2/4处急剧阈值$。我们通过为某些$ n = \ omega（\，d^2/\ log^5（d）\，）$构建合适的椭圆形来解决这个猜想，从而改善了Ghosh等人的先前工作。 [Proc。关于计算机科学基础的研讨会，第954-965、2020页]，需要$ n = o（d^{3/2}）$。我们的证明证明了Saunderson等人的最小二乘结构的可行性。使用对特定非标准随机矩阵的特征向量和特征值进行仔细的分析。

Suppose we are given an $n$-dimensional order-3 symmetric tensor $T \in (\mathbb{R}^n)^{\otimes 3}$ that is the sum of $r$ random rank-1 terms. The problem of recovering the rank-1 components is possible in principle when $r \lesssim n^2$ but polynomial-time algorithms are only known in the regime $r \ll n^{3/2}$. Similar "statistical-computational gaps" occur in many high-dimensional inference tasks, and in recent years there has been a flurry of work on explaining the apparent computational hardness in these problems by proving lower bounds against restricted (yet powerful) models of computation such as statistical queries (SQ), sum-of-squares (SoS), and low-degree polynomials (LDP). However, no such prior work exists for tensor decomposition, largely because its hardness does not appear to be explained by a "planted versus null" testing problem. We consider a model for random order-3 tensor decomposition where one component is slightly larger in norm than the rest (to break symmetry), and the components are drawn uniformly from the hypercube. We resolve the computational complexity in the LDP model: $O(\log n)$-degree polynomial functions of the tensor entries can accurately estimate the largest component when $r \ll n^{3/2}$ but fail to do so when $r \gg n^{3/2}$. This provides rigorous evidence suggesting that the best known algorithms for tensor decomposition cannot be improved, at least by known approaches. A natural extension of the result holds for tensors of any fixed order $k \ge 3$, in which case the LDP threshold is $r \sim n^{k/2}$.

高维统计数据的一个基本目标是检测或恢复嘈杂数据中隐藏的种植结构（例如低级别矩阵）。越来越多的工作研究低级多项式作为此类问题的计算模型的限制模型：在各种情况下，数据的低级多项式可以与最知名的多项式时间算法的统计性能相匹配。先前的工作已经研究了低度多项式的力量，以检测隐藏结构的存在。在这项工作中，我们将这些方法扩展到解决估计和恢复问题（而不是检测）。对于大量的“信号加噪声”问题，我们给出了一个用户友好的下限，以获得最佳的均衡误差。据我们所知，这些是建立相关检测问题的恢复问题低度硬度的第一个结果。作为应用，我们对种植的子静脉和种植的密集子图问题的低度最小平方误差进行了严格的特征，在两种情况下都解决了有关恢复的计算复杂性的开放问题（在低度框架中）。

我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法，用于辅助性Subgaussian分布。在这项工作中，我们开发了第一个有效的算法，用于强大的稀疏平均值估计，而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布，带有“认证有限”的$ t $ tum-矩和足够轻的尾巴，我们的算法达到了$ o（\ epsilon^{1-1/t}）$带有样品复杂性$的错误（\ epsilon^{1-1/t}） m =（k \ log（d））^{o（t）}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况，我们的算法达到了$ \ tilde o（\ epsilon）$的接近最佳错误，带有样品复杂性$ m = o（k^4 \ mathrm {polylog}（d）（d））/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和，对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限，提供了证据，表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。

我们重新审视量子状态认证的基本问题：给定混合状态$ \ rho \中的副本\ mathbb {c} ^ {d \ times d} $和混合状态$ \ sigma $的描述，决定是否$ \ sigma = \ rho $或$ \ | \ sigma - \ rho \ | _ {\ mathsf {tr}} \ ge \ epsilon $。当$ \ sigma $最大化时，这是混合性测试，众所周知，$ \ omega（d ^ {\ theta（1）} / \ epsilon ^ 2）$副本是必要的，所以确切的指数取决于测量类型学习者可以使[OW15，BCL20]，并且在许多这些设置中，有一个匹配的上限[OW15，Bow19，BCL20]。可以避免这种$ d ^ {\ theta（1）} $依赖于某些类型的混合状态$ \ sigma $，例如。大约低等级的人？更常见地，是否存在一个简单的功能$ f：\ mathbb {c} ^ {d \ times d} \ to \ mathbb {r} _ {\ ge 0} $，其中一个人可以显示$ \ theta（f（ \ sigma）/ \ epsilon ^ 2）$副本是必要的，并且足以就任何$ \ sigma $的国家认证？这种实例 - 最佳边界在经典分布测试的背景下是已知的，例如， [VV17]。在这里，我们为量子设置提供了这个性质的第一个界限，显示（达到日志因子），即使用非接受不连贯测量的状态认证的复杂性复杂性基本上是通过复制复杂性进行诸如$ \ sigma $之间的保真度的复杂性。和最大混合的状态。令人惊讶的是，我们的界限与经典问题的实例基本上不同，展示了两个设置之间的定性差异。

随机奇异值分解（RSVD）是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $，原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数，$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中，我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性，即，观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $（频谱规范）和$ \ ell_ {2 \ to \ infty} $（最大行行列$ \ ell_2 $ norm）$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比（SNR）和功率迭代$ g $的数量。观察到一个相变现象，其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明，每当噪声矩阵满足一定的痕量生长条件时，这些相变发生的$ g $的阈值都会很清晰。最后，我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

我们研究了学习哈密顿$ h $ to precision $ \ varepsilon $的问题，假设我们将获得其gibbs state $ \ rho = \ exp（ - \ beta h）/\ operatoratorname {tr}（\ exp（\ exp）（ - \ beta h））$在已知的反温度$ \ beta $处。 Anshu，Arunachalam，Kuwahara和Soleimanifar（Nature Physics，2021，Arxiv：2004.07266）最近研究了此问题的样品复杂性（需要$ \ rho $的副本数量）。在高温（低$ \ beta $）制度中，他们的算法具有样品复杂性poly poly $（n，1/\ beta，1/\ varepsilon）$，并且可以用多项式但次优的时间复杂性实现。在本文中，我们研究了更一般的哈密顿人的同样问题。我们展示了如何学习哈密顿量的系数到错误$ \ varepsilon $带有样本复杂性$ s = o（\ log n/（\ beta \ varepsilon）^{2}）$和样本大小的时间复杂性，$ o（s n）$。此外，我们证明了匹配的下限，表明我们算法的样品复杂性是最佳的，因此我们的时间复杂性也是最佳的。在附录中，我们证明，几乎可以使用相同的算法来从实时进化的统一$ e^{ - it H} $中学习$ h $，其中具有相似的示例和时间复杂性的小$ t $制度。

假设$ g $是根据所谓的HyperGraph随机块模型（HSBM）产生的，我们考虑了稀疏$ Q $均匀的HyperGraph $ G $中的社区检测问题。我们证明，基于非折线操作员的光谱方法具有很高的概率，可以降低到Angelini等人猜想的广义kesten-Stigum检测阈值。我们表征了稀疏HSBM的非背带操作员的频谱，并使用Ihara-Bass公式为超图提供有效的尺寸降低程序。结果，可以将稀疏HSBM的社区检测减少为$ 2N \ times 2n $非正态矩阵的特征向量问题，该矩阵从邻接矩阵和超级格雷普的学位矩阵中构建。据我们所知，这是第一种可证明，有效的光谱算法，它可以根据一般对称概率张量生成$ K $块的HSBMS阈值。

在这项工作中，我们研究了一个非负矩阵分解的变体，我们希望找到给定输入矩阵的对称分解成稀疏的布尔矩阵。正式说话，给定$ \ mathbf {m} \ in \ mathbb {z} ^ {m \ times m} $，我们想找到$ \ mathbf {w} \ in \ {0,1 \} ^ {m \ times $} $这样$ \ | \ mathbf {m} - \ mathbf {w} \ mathbf {w} ^ \ top \ | _0 $在所有$ \ mathbf {w} $中最小化为$ k $ -parse。这个问题结果表明与恢复线图中的超图以及私人神经网络训练的重建攻击相比密切相关。由于这个问题在最坏的情况下，我们研究了在这些重建攻击的背景下出现的自然平均水平变体：$ \ mathbf {m} = \ mathbf {w} \ mathbf {w} ^ {\ top $ \ mathbf {w} $ \ mathbf {w} $ k $ -parse行的随机布尔矩阵，目标是恢复$ \ mathbf {w} $上列排列。等效，这可以被认为是从其线图中恢复均匀随机的k $ k $。我们的主要结果是基于对$ \ MATHBF {W} $的引导高阶信息的此问题的多项式算法，然后分解适当的张量。我们分析中的关键成分，可能是独立的兴趣，是表示这种矩阵$ \ mathbf {w} $在$ m = \ widetilde {\ omega}（r）时，这一矩阵$ \ mathbf {w} $具有高概率。 $，我们使用Littlewood-Offord理论的工具和二进制Krawtchouk多项式的估算。

我们研究了小组测试问题，其目标是根据合并测试的结果，确定一组k感染的人，这些k含有稀有疾病，这些人在经过测试中至少有一个受感染的个体时返回阳性的结果。团体。我们考虑将个人分配给测试的两个不同的简单随机过程：恒定柱设计和伯努利设计。我们的第一组结果涉及基本统计限制。对于恒定柱设计，我们给出了一个新的信息理论下限，这意味着正确识别的感染者的比例在测试数量越过特定阈值时会经历急剧的“全或全或无所不包”的相变。对于Bernoulli设计，我们确定解决相关检测问题所需的确切测试数量（目的是区分小组测试实例和纯噪声），改善Truong，Aldridge和Scarlett的上限和下限（2020）。对于两个小组测试模型，我们还研究了计算有效（多项式时间）推理程序的能力。我们确定了解决检测问题的低度多项式算法所需的精确测试数量。这为在少量稀疏度的检测和恢复问题中都存在固有的计算统计差距提供了证据。值得注意的是，我们的证据与Iliopoulos和Zadik（2021）相反，后者预测了Bernoulli设计中没有计算统计差距。

我们研究量子存储器的力量，以了解量子系统和动态的学习性质，这在物理和化学方面具有重要意义。许多最先进的学习算法需要访问额外的外部量子存储器。虽然这种量子存储器不需要先验，但在许多情况下，不利用量子存储器的算法需要比那些更多样的数据。我们表明，这种权衡在各种学习问题中是固有的。我们的结果包括以下内容：（1）我们显示以$ M $ -Qubit状态Rho执行暗影断层扫描，以M $观察到，任何没有量子存储器的算法需要$ \ omega（\ min（m，2 ^ n） ）最坏情况下Rho的标准。达到对数因子，这与[HKP20]的上限匹配，完全解决了[AAR18，AR19]中的打开问题。 （2）我们在具有和不具有量子存储器之间的算法之间建立指数分离，用于纯度测试，区分扰扰和去极化的演变，以及在物理动态中揭示对称性。我们的分离通过允许更广泛的无量子存储器的算法来改善和概括[ACQ21]的工作。 （3）我们提供量子存储器和样本复杂性之间的第一个权衡。我们证明，估计所有$ N $ -Qubit Pauli可观察到的绝对值，Qumum Memory的$ K <N $ Qubits的算法需要至少$ \ omega（2 ^ {（nk）/ 3}）$样本，但在那里是使用$ n $ -Qubit量子存储器的算法，该算法只需要$ o（n）$ samples。我们展示的分离足够大，并且可能已经是显而易见的，例如，数十Qubits。这提供了一种具体的路径，朝着使用量子存储器学习算法的实际优势。

现代神经网络通常以强烈的过度构造状态运行：它们包含许多参数，即使实际标签被纯粹随机的标签代替，它们也可以插入训练集。尽管如此，他们在看不见的数据上达到了良好的预测错误：插值训练集并不会导致巨大的概括错误。此外，过度散色化似乎是有益的，因为它简化了优化景观。在这里，我们在神经切线（NT）制度中的两层神经网络的背景下研究这些现象。我们考虑了一个简单的数据模型，以及各向同性协变量的矢量，$ d $尺寸和$ n $隐藏的神经元。我们假设样本量$ n $和尺寸$ d $都很大，并且它们在多项式上相关。我们的第一个主要结果是对过份术的经验NT内核的特征结构的特征。这种表征意味着必然的表明，经验NT内核的最低特征值在$ ND \ gg n $后立即从零界限，因此网络可以在同一制度中精确插值任意标签。我们的第二个主要结果是对NT Ridge回归的概括误差的表征，包括特殊情况，最小值-ULL_2 $ NORD插值。我们证明，一旦$ nd \ gg n $，测试误差就会被内核岭回归之一相对于无限宽度内核而近似。多项式脊回归的误差依次近似后者，从而通过与激活函数的高度组件相关的“自我诱导的”项增加了正则化参数。多项式程度取决于样本量和尺寸（尤其是$ \ log n/\ log d $）。

Motivated by the problem of matching vertices in two correlated Erd\H{o}s-R\'enyi graphs, we study the problem of matching two correlated Gaussian Wigner matrices. We propose an iterative matching algorithm, which succeeds in polynomial time as long as the correlation between the two Gaussian matrices does not vanish. Our result is the first polynomial time algorithm that solves a graph matching type of problem when the correlation is an arbitrarily small constant.

在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法，该算法可以忍受$ \ epsilon $ - 损坏和达到错误$ o（\ epsilon） + e^{ - \ frac {c} {2} {2}（1 \ pm o（1））} $其中$ c =（\ sqrt {a} - \ sqrt {b}）^2 $是信噪比，$ a/n $和$ b/n $是互发和intra-intra-intra-社区连接概率分别。这些界限基本上与无损坏的SBM的最小值相匹配。我们还为$ \ mathbb {z} _2 $ -Synchronization提供了可靠的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限制的单调变化混合在一起，从半随机模型中。

矩阵正常模型，高斯矩阵变化分布的系列，其协方差矩阵是两个较低尺寸因子的Kronecker乘积，经常用于模拟矩阵变化数据。张量正常模型将该家庭推广到三个或更多因素的Kronecker产品。我们研究了矩阵和张量模型中协方差矩阵的Kronecker因子的估计。我们向几个自然度量中的最大似然估计器（MLE）实现的误差显示了非因素界限。与现有范围相比，我们的结果不依赖于条件良好或稀疏的因素。对于矩阵正常模型，我们所有的所有界限都是最佳的对数因子最佳，对于张量正常模型，我们对最大因数和整体协方差矩阵的绑定是最佳的，所以提供足够的样品以获得足够的样品以获得足够的样品常量Frobenius错误。在与我们的样本复杂性范围相同的制度中，我们表明迭代程序计算称为触发器算法称为触发器算法的MLE的线性地收敛，具有高概率。我们的主要工具是Fisher信息度量诱导的正面矩阵的几何中的测地强凸性。这种强大的凸起由某些随机量子通道的扩展来决定。我们还提供了数值证据，使得将触发器算法与简单的收缩估计器组合可以提高缺乏采样制度的性能。

我们根据计算一个扎根于每个顶点的某个加权树的家族而构成的相似性得分提出了一种有效的图形匹配算法。对于两个erd \ h {o} s-r \'enyi图$ \ mathcal {g}（n，q）$，其边缘通过潜在顶点通信相关联，我们表明该算法正确地匹配了所有范围的范围，除了所有的vertices分数外，有了很高的概率，前提是$ nq \ to \ infty $，而边缘相关系数$ \ rho $满足$ \ rho^2> \ alpha \ ailpha \大约0.338 $，其中$ \ alpha $是Otter的树木计数常数。此外，在理论上是必需的额外条件下，可以精确地匹配。这是第一个以显式常数相关性成功的多项式图匹配算法，并适用于稀疏和密集图。相比之下，以前的方法要么需要$ \ rho = 1-o（1）$，要么仅限于稀疏图。该算法的症结是一个经过精心策划的植根树的家族，称为吊灯，它可以有效地从同一树的计数中提取图形相关性，同时抑制不同树木之间的不良相关性。

我们考虑了在高维度中平均分离的高斯聚类混合物的问题。我们是从$ k $身份协方差高斯的混合物提供的样本，使任何两对手段之间的最小成对距离至少为$ \ delta $，对于某些参数$ \ delta> 0 $，目标是恢复这些样本的地面真相聚类。它是分离$ \ delta = \ theta（\ sqrt {\ log k}）$既有必要且足以理解恢复良好的聚类。但是，实现这种担保的估计值效率低下。我们提供了在多项式时间内运行的第一算法，几乎符合此保证。更确切地说，我们给出了一种算法，它需要多项式许多样本和时间，并且可以成功恢复良好的聚类，只要分离为$ \ delta = \ oomega（\ log ^ {1/2 + c} k）$ ，任何$ c> 0 $。以前，当分离以k $的分离和可以容忍$ \ textsf {poly}（\ log k）$分离所需的quasi arynomial时间时，才知道该问题的多项式时间算法。我们还将我们的结果扩展到分布的分布式的混合物，该分布在额外的温和假设下满足Poincar \ {e}不等式的分布。我们认为我们相信的主要技术工具是一种新颖的方式，可以隐含地代表和估计分配的​​高度时刻，这使我们能够明确地提取关于高度时刻的重要信息而没有明确地缩小全瞬间张量。

我们考虑估计与I.I.D的排名$ 1 $矩阵因素的问题。高斯，排名$ 1 $的测量值，这些测量值非线性转化和损坏。考虑到非线性的两种典型选择，我们研究了从随机初始化开始的此非convex优化问题的天然交流更新规则的收敛性能。我们通过得出确定性递归，即使在高维问题中也是准确的，我们显示出算法的样本分割版本的敏锐收敛保证。值得注意的是，虽然无限样本的种群更新是非信息性的，并提示单个步骤中的精确恢复，但算法 - 我们的确定性预测 - 从随机初始化中迅速地收敛。我们尖锐的非反应分析也暴露了此问题的其他几种细粒度，包括非线性和噪声水平如何影响收敛行为。从技术层面上讲，我们的结果可以通过证明我们的确定性递归可以通过我们的确定性顺序来预测我们的确定性序列，而当每次迭代都以$ n $观测来运行时，我们的确定性顺序可以通过$ n^{ - 1/2} $的波动。我们的技术利用了源自有关高维$ m $估计文献的遗留工具，并为通过随机数据的其他高维优化问题的随机初始化而彻底地分析了高阶迭代算法的途径。