近似消息传递（AMP）是具有非高斯分布的某些高维线性系统的低成本迭代参数估计技术。然而，放大器仅适用于独立相同的分布（IID）变换矩阵，但是对于其他矩阵集合，尤其是对于不良条件的矩阵，可能变得不可靠（例如，表现不良或甚至不同）。建议正交/矢量放大器（OAMP / VAMP）用于一般右单一不变的矩阵来处理这种困难。然而，贝叶斯最优休息/鞋面（BO-OAMP / VAMP）需要高度复杂性线性最小均方误差（MMSE）估计器。这限制了oamp / vamp在大规模系统中的应用。为了解决AMP和BO-OAMP / VAMP的缺点，本文提出了在正交原理下的记忆放大器（MAMP）框架，保证了MAMP中估计估计误差的渐近IID高斯。我们为本域内存估算器提供了一个正交化过程，以实现MAMP所需的正交性。此外，我们提出了一种贝叶斯 - 最佳机制（BO-MAMP），其中提出了一种用于干扰抑制的长存储器匹配过滤器。 BO-MAMP的复杂性与AMP相当。源于渐近表征Bo-MAMP的性能的状态演变。基于国家演化，优化了BO-MAMP中的松弛参数和阻尼载体。对于所有右单一不变的矩阵，优化的BO-MAMP的状态演变会收敛到与高复杂性BO-OAMP / VAMP相同的固定点，并且如果其状态进化具有独特的固定点，则是贝叶斯的最佳状态。最后，提供了模拟以验证理论结果的有效性和准确性。

近似消息传递（AMP）是一种希望具有非高斯信令的某些高维线性系统的未知信号重建的有希望的技术。 AMP型算法的杰出特征是它们的动态可以通过状态演进来严格描述。但是，状态的进化不一定保证迭代算法的融合。为了解决AMP型算法的收敛问题原则上，本文提出了一种在足够的统计条件下的存储放大器（MAMP），命名为足够的统计MAMP（SS-MAMP）。我们表明SS-MAMP的协方差矩阵是L-带状和会聚。考虑到任意的MAMP，我们可以通过阻尼构造SS-MAMP，这不仅可以确保MAMP的收敛，而且还可以保留MAMP的正交性，即，其动态可以通过状态演变严格地描述。作为副产品，我们证明贝叶斯最佳正交/载体放大器（Bo-Oamp / Vamp）是SS-MAMP。结果，我们揭示了大型系统的Bo-Oamp /鞋面的两个有趣特性：1）协方差矩阵是L型带状的，并且在BO-Oamp / vamp中收敛，2）阻尼和存储器无用（即，做在BO-OAMP / VAMP中没有带来性能改进。作为一个例子，我们构建了一个足够的统计贝叶斯 - 最佳MAMP（BO-MAMP），如果其状态进化具有独特的固定点，并且其MSE比原来的BO-MAMP更糟糕，那么它是最佳的。最后，提供了模拟以验证理论结果的有效性和准确性。

近似消息传递（AMP）类型算法已被广泛用于某些大型随机线性系统的信号重建。AMP型算法的关键特征是可以通过状态进化正确描述其动力学。但是，状态进化不一定保证迭代算法的收敛性。为了解决原则上AMP类型算法的收敛问题，本文提出了在足够的统计条件下的记忆AMP（MAMP），称为足够的统计MAMP（SS-MAMP）。我们表明，SS-MAMP的协方差矩阵是L带和收敛的。给定任意启动，我们可以通过阻尼来构建SS-MAMP，这不仅可以确保收敛性，而且可以保留正交性，即可以通过状态进化正确描述其动力学。

本文研究了一个涉及单位不变的传感矩阵，任意固定信号分布和正向误差控制（FEC）编码的大型单位不变系统（LUI）。基于未编码的路易斯中正交近似消息传递（OAMP）的状态进化建立了几种面积属性。在假设关节和FEC解码的状态进化是正确的，并且复制方法是可靠的，我们分析了可实现的OAMP速率。我们证明，OAMP通过基于匹配的FEC编码的任意信号分布来达到LUI的复制方法预测的约束能力。同时，我们详细阐述了LUI的约束能力成绩的编码原理，基于该编码原理，基于其不规则的低密度均衡检查（LDPC）代码在模拟结果中针对二进制信号进行了优化。我们表明，使用优化代码的OAMP比未优化的代码和著名的涡轮线性MMSE算法具有显着的性能提高。对于正交相移键合（QPSK）调制，在各种通道条件下观察到容量限制的位错误率（BER）性能。

我们考虑一个非线性逆问题$ \ mathbf {y} = f（\ mathbf {ax}）$，其中观察$ \ mathbf {y} \ in \ mathbb {r} ^ m $ in $ \ mathbf的组件非线性转换\ MathBB {R} ^ M $，$ \ MATHBF {X} \ IN \ MATHBB {R} ^ $是兴趣的信号，$ \ MATHBF {A} $是已知的线性映射。通过正确指定非线性处理功能，可以将该模型统治到许多信号处理问题，包括压缩感测和相位检索。我们本文的主要目标是了解传感矩阵的影响，或更具体地是感测矩阵的频谱，难以从$ \ mathbf {y} $恢复$ \ mathbf {x} $。为了实现这一目标，我们研究了最成功的恢复方法之一的性能，即期望传播算法（EP）。我们为$ \ mathbf {a} $的频谱的尖端定义了一个概念，并显示了在EP性能方面的这一措施的重要性。频谱的刺激是否可以伤害或帮助EP的恢复性能取决于$ F $。我们根据函数$ F $定义某些数量，使我们能够描述谱对EP恢复刺激的影响。基于我们的框架，我们能够表明，例如，在阶段检索问题中，具有尖光频谱的矩阵对于EP更好，而在1位压缩的感测问题中，较少的尖峰（平坦）频谱提供更好的恢复。我们的结果统一并基本上概括了比较子高斯和正交矩阵的现有结果，并为设计最佳感测系统提供平台。

我们考虑通过旋转不变设计矩阵定义的广义线性模型中信号估计的问题。由于这些矩阵可以具有任意光谱分布，因此该模型非常适合于捕获在应用中经常出现的复杂相关结构。我们提出了一种新颖的近似消息，用于通过（AMP）算法用于信号估计，并且经由状态演进递归严格地表征其在高维极限中的性能。假设设计矩阵频谱的知识，我们的旋转不变放大器具有与高斯矩阵的现有放大器相同的顺序的复杂性;它还恢复现有的放大器作为一个特例。数值结果展示了靠近向量放大器的性能（在某些设置中猜测贝叶斯 - 最佳），但随着所提出的算法不需要计算昂贵的奇异值分解，可以获得更低的复杂性。

Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.

最近有兴趣的兴趣在教师学生环境中的各种普遍性线性估计问题中的渐近重建性能研究，特别是对于I.I.D标准正常矩阵的案例。在这里，我们超越这些矩阵，并证明了具有具有任意界限频谱的旋转不变数据矩阵的凸遍的线性模型的重建性能的分析公式，严格地确认使用来自统计物理的副本衍生的猜想。该公式包括许多问题，例如压缩感测或稀疏物流分类。通过利用消息通过算法和迭代的统计特性来实现证明，允许表征估计器的渐近实证分布。我们的证据是基于构建Oracle多层向量近似消息传递算法的会聚序列的构建，其中通过检查等效动态系统的稳定性来完成收敛分析。我们说明了我们对主流学习方法的数值示例的要求，例如稀疏的逻辑回归和线性支持矢量分类器，显示中等大小模拟和渐近预测之间的良好一致性。

这项调查旨在提供线性模型及其背后的理论的介绍。我们的目标是对读者进行严格的介绍，并事先接触普通最小二乘。在机器学习中，输出通常是输入的非线性函数。深度学习甚至旨在找到需要大量计算的许多层的非线性依赖性。但是，这些算法中的大多数都基于简单的线性模型。然后，我们从不同视图中描述线性模型，并找到模型背后的属性和理论。线性模型是回归问题中的主要技术，其主要工具是最小平方近似，可最大程度地减少平方误差之和。当我们有兴趣找到回归函数时，这是一个自然的选择，该回归函数可以最大程度地减少相应的预期平方误差。这项调查主要是目的的摘要，即线性模型背后的重要理论的重要性，例如分布理论，最小方差估计器。我们首先从三种不同的角度描述了普通的最小二乘，我们会以随机噪声和高斯噪声干扰模型。通过高斯噪声，该模型产生了可能性，因此我们引入了最大似然估计器。它还通过这种高斯干扰发展了一些分布理论。最小二乘的分布理论将帮助我们回答各种问题并引入相关应用。然后，我们证明最小二乘是均值误差的最佳无偏线性模型，最重要的是，它实际上接近了理论上的极限。我们最终以贝叶斯方法及以后的线性模型结束。

诸如压缩感测，图像恢复，矩阵/张恢复和非负矩阵分子等信号处理和机器学习中的许多近期问题可以作为约束优化。预计的梯度下降是一种解决如此约束优化问题的简单且有效的方法。本地收敛分析将我们对解决方案附近的渐近行为的理解，与全球收敛分析相比，收敛率的较小界限提供了较小的界限。然而，本地保证通常出现在机器学习和信号处理的特定问题领域。此稿件在约束最小二乘范围内，对投影梯度下降的局部收敛性分析提供了统一的框架。该建议的分析提供了枢转局部收敛性的见解，例如线性收敛的条件，收敛区域，精确的渐近收敛速率，以及达到一定程度的准确度所需的迭代次数的界限。为了证明所提出的方法的适用性，我们介绍了PGD的收敛分析的配方，并通过在四个基本问题上的配方的开始延迟应用来证明它，即线性约束最小二乘，稀疏恢复，最小二乘法使用单位规范约束和矩阵完成。

我们调查与高斯的混合的数据分享共同但未知，潜在虐待协方差矩阵的数据。我们首先考虑具有两个等级大小的组件的高斯混合，并根据最大似然估计导出最大切割整数程序。当样品的数量在维度下线性增长时，我们证明其解决方案实现了最佳的错误分类率，直到对数因子。但是，解决最大切割问题似乎是在计算上棘手的。为了克服这一点，我们开发了一种高效的频谱算法，该算法达到最佳速率，但需要一种二次样本量。虽然这种样本复杂性比最大切割问题更差，但我们猜测没有多项式方法可以更好地执行。此外，我们收集了支持统计计算差距存在的数值和理论证据。最后，我们将MAX-CUT程序概括为$ k $ -means程序，该程序处理多组分混合物的可能性不平等。它享有相似的最优性保证，用于满足运输成本不平等的分布式的混合物，包括高斯和强烈的对数的分布。

随机奇异值分解（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的几乎最佳性能保证在应用于三个统计推断问题的情况下，即社区检测，矩阵完成和主要的组件分析，并使用缺失的数据来说明我们的理论结果。

In a mixed generalized linear model, the objective is to learn multiple signals from unlabeled observations: each sample comes from exactly one signal, but it is not known which one. We consider the prototypical problem of estimating two statistically independent signals in a mixed generalized linear model with Gaussian covariates. Spectral methods are a popular class of estimators which output the top two eigenvectors of a suitable data-dependent matrix. However, despite the wide applicability, their design is still obtained via heuristic considerations, and the number of samples $n$ needed to guarantee recovery is super-linear in the signal dimension $d$. In this paper, we develop exact asymptotics on spectral methods in the challenging proportional regime in which $n, d$ grow large and their ratio converges to a finite constant. By doing so, we are able to optimize the design of the spectral method, and combine it with a simple linear estimator, in order to minimize the estimation error. Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms. Numerical simulations for mixed linear regression and phase retrieval display the advantage enabled by our analysis over existing designs of spectral methods.

我们介绍树-AMP，站在树近似消息传递，用于高维树结构模型的组成推理的Python包。该包提供统一框架，用于研究以前导出的多种机器学习任务的几种近似消息传递算法，例如广义线性模型，多层网络的推断，矩阵分解和使用不可惩罚的重建。对于某些型号，可以通过状态进化理论上预测算法的渐近性能，并通过自由熵形式主义估计的测量熵。通过设计模块化：实现因子的每个模块可以与其他模块一起组成，以解决复杂的推理任务。用户只需要声明模型的因子图：推理算法，状态演化和熵估计是完全自动化的。

套索是一种高维回归的方法，当时，当协变量$ p $的订单数量或大于观测值$ n $时，通常使用它。由于两个基本原因，经典的渐近态性理论不适用于该模型：$（1）$正规风险是非平滑的； $（2）$估算器$ \ wideHat {\ boldsymbol {\ theta}} $与true参数vector $ \ boldsymbol {\ theta}^*$无法忽略。结果，标准的扰动论点是渐近正态性的传统基础。另一方面，套索估计器可以精确地以$ n $和$ p $大，$ n/p $的订单为一。这种表征首先是在使用I.I.D的高斯设计的情况下获得的。协变量：在这里，我们将其推广到具有非偏差协方差结构的高斯相关设计。这是根据更简单的``固定设计''模型表示的。我们在两个模型中各种数量的分布之间的距离上建立了非反应界限，它们在合适的稀疏类别中均匀地固定在信号上$ \ boldsymbol {\ theta}^*$。作为应用程序，我们研究了借助拉索的分布，并表明需要校正程度对于计算有效的置信区间是必要的。

我们提供了新的基于梯度的方法，以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f：\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题，它是隐含的可分解的，作为$ m $未知的非交互方式的总和，强烈的凸起功能并提供方法这解决了这个问题，这些问题是缩放（最快的对数因子）作为组件的条件数量的平方根的乘积。这种复杂性绑定（我们证明几乎是最佳的）可以几乎指出的是加速梯度方法的几乎是指数的，这将作为$ F $的条件数量的平方根。此外，我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解（这将是过度昂贵的），而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}（d m）$空间，在数字上稳定，并打开门以更细粒度的了解凸优化超出条件号的复杂性。

统计推断中的主要范式取决于I.I.D.的结构。来自假设的无限人群的数据。尽管它取得了成功，但在复杂的数据结构下，即使在清楚无限人口所代表的内容的情况下，该框架在复杂的数据结构下仍然不灵活。在本文中，我们探讨了一个替代框架，在该框架中，推断只是对模型误差的不变性假设，例如交换性或符号对称性。作为解决这个不变推理问题的一般方法，我们提出了一个基于随机的过程。我们证明了该过程的渐近有效性的一般条件，并在许多数据结构中说明了，包括单向和双向布局中的群集误差。我们发现，通过残差随机化的不变推断具有三个吸引人的属性：（1）在弱且可解释的条件下是有效的，可以解决重型数据，有限聚类甚至一些高维设置的问题。 （2）它在有限样品中是可靠的，因为它不依赖经典渐近学所需的规律性条件。 （3）它以适应数据结构的统一方式解决了推断问题。另一方面，诸如OLS或Bootstrap之类的经典程序以I.I.D.为前提。结构，只要实际问题结构不同，就需要修改。经典框架中的这种不匹配导致了多种可靠的误差技术和自举变体，这些变体经常混淆应用研究。我们通过广泛的经验评估证实了这些发现。残留随机化对许多替代方案的表现有利，包括可靠的误差方法，自举变体和分层模型。

This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models-including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation-which exploits a certain tensor structure in their low-order observable moments (typically, of second-and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.

教师 - 学生模型提供了一个框架，其中可以以封闭形式描述高维监督学习的典型情况。高斯I.I.D的假设然而，可以认为典型教师 - 学生模型的输入数据可以被认为过于限制，以捕获现实数据集的行为。在本文中，我们介绍了教师和学生可以在不同的空格上行动的模型的高斯协变态概括，以固定的，而是通用的特征映射。虽然仍处于封闭形式的仍然可解决，但这种概括能够捕获广泛的现实数据集的学习曲线，从而兑现师生框架的潜力。我们的贡献是两倍：首先，我们证明了渐近培训损失和泛化误差的严格公式。其次，我们呈现了许多情况，其中模型的学习曲线捕获了使用内​​核回归和分类学习的现实数据集之一，其中盒出开箱特征映射，例如随机投影或散射变换，或者与散射变换预先学习的 - 例如通过培训多层神经网络学到的特征。我们讨论了框架的权力和局限性。

对于由缺陷线性回归中的标签噪声引起的预期平均平方概率，我们证明了无渐近分布的下限。我们的下部结合概括了过度公共数据（内插）制度的类似已知结果。与最先前的作品相比，我们的分析适用于广泛的输入分布，几乎肯定的全排列功能矩阵，允许我们涵盖各种类型的确定性或随机特征映射。我们的下限是渐近的锐利，暗示在存在标签噪声时，缺陷的线性回归不会在任何这些特征映射中围绕内插阈值进行良好的。我们详细分析了强加的假设，并为分析（随机）特征映射提供了理论。使用此理论，我们可以表明我们的假设对于具有（Lebesgue）密度的输入分布以及随机深神经网络给出的特征映射，具有Sigmoid，Tanh，SoftPlus或Gelu等分析激活功能。作为进一步的例子，我们示出了来自随机傅里叶特征和多项式内核的特征映射也满足我们的假设。通过进一步的实验和分析结果，我们补充了我们的理论。