在本文中，我们提供了有关Hankel低级近似和完成工作的综述和书目，特别强调了如何将这种方法用于时间序列分析和预测。我们首先描述问题的可能表述，并就获得全球最佳解决方案的相关主题和挑战提供评论。提供了关键定理，并且纸张以一些说明性示例关闭。

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard, because it contains vector cardinality minimization as a special case.In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum rank solution can be recovered by solving a convex optimization problem, namely the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is Ω(r(m + n) log mn), where m, n are the dimensions of the matrix, and r is its rank.The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this pre-existing concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization. We also discuss several algorithmic approaches to solving the norm minimization relaxations, and illustrate our results with numerical examples.

We investigate the problem of recovering a partially observed high-rank matrix whose columns obey a nonlinear structure such as a union of subspaces, an algebraic variety or grouped in clusters. The recovery problem is formulated as the rank minimization of a nonlinear feature map applied to the original matrix, which is then further approximated by a constrained non-convex optimization problem involving the Grassmann manifold. We propose two sets of algorithms, one arising from Riemannian optimization and the other as an alternating minimization scheme, both of which include first- and second-order variants. Both sets of algorithms have theoretical guarantees. In particular, for the alternating minimization, we establish global convergence and worst-case complexity bounds. Additionally, using the Kurdyka-Lojasiewicz property, we show that the alternating minimization converges to a unique limit point. We provide extensive numerical results for the recovery of union of subspaces and clustering under entry sampling and dense Gaussian sampling. Our methods are competitive with existing approaches and, in particular, high accuracy is achieved in the recovery using Riemannian second-order methods.

In this paper, we consider the estimation of a low Tucker rank tensor from a number of noisy linear measurements. The general problem covers many specific examples arising from applications, including tensor regression, tensor completion, and tensor PCA/SVD. We consider an efficient Riemannian Gauss-Newton (RGN) method for low Tucker rank tensor estimation. Different from the generic (super)linear convergence guarantee of RGN in the literature, we prove the first local quadratic convergence guarantee of RGN for low-rank tensor estimation in the noisy setting under some regularity conditions and provide the corresponding estimation error upper bounds. A deterministic estimation error lower bound, which matches the upper bound, is provided that demonstrates the statistical optimality of RGN. The merit of RGN is illustrated through two machine learning applications: tensor regression and tensor SVD. Finally, we provide the simulation results to corroborate our theoretical findings.

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets.This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed-either explicitly or implicitly-to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m × n matrix. (i) For a dense input matrix, randomized algorithms require O(mn log(k)) floating-point operations (flops) in contrast with O(mnk) for classical algorithms. (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multi-processor architectures. (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data.

在本文中，我们提出{\ it \下划线{r} ecursive} {\ it \ usef \ undesline {i} mortance} {\ it \ it \ usew supsline {s} ketching} algorithM squares {\ it \下划线{o} ptimization}（risro）。 Risro的关键步骤是递归重要性草图，这是一个基于确定性设计的递归投影的新素描框架，它与文献中的随机素描\ Citep {Mahoney2011 randomized，Woodruff2014sketching}有很大不同。在这个新的素描框架下，可以重新解释文献中的几种现有算法，而Risro比它们具有明显的优势。 Risro易于实现，并在计算上有效，其中每次迭代中的核心过程是解决降低尺寸最小二乘问题的问题。我们在某些轻度条件下建立了Risro的局部二次线性和二次收敛速率。我们还发现了Risro与Riemannian Gauss-Newton算法在固定等级矩阵上的联系。在机器学习和统计数据中的两种应用中，RISRO的有效性得到了证明：低级别矩阵痕量回归和相位检索。仿真研究证明了Risro的出色数值性能。

我们研究了张量张量的回归，其中的目标是将张量的响应与张量协变量与塔克等级参数张量/矩阵连接起来，而没有其内在等级的先验知识。我们提出了Riemannian梯度下降（RGD）和Riemannian Gauss-Newton（RGN）方法，并通过研究等级过度参数化的影响来应对未知等级的挑战。我们通过表明RGD和RGN分别线性地和四边形地收敛到两个等级的统计最佳估计值，从而为一般的张量调节回归提供了第一个收敛保证。我们的理论揭示了一种有趣的现象：Riemannian优化方法自然地适应了过度参数化，而无需修改其实施。我们还为低度多项式框架下的标量调整回归中的统计计算差距提供了第一个严格的证据。我们的理论证明了``统计计算差距的祝福''现象：在张张量的张量回归中，对于三个或更高的张紧器，在张张量的张量回归中，计算所需的样本量与中等级别相匹配的计算量相匹配。在考虑计算可行的估计器时，虽然矩阵设置没有此类好处。这表明中等等级的过度参数化本质上是``在张量调整的样本量三分或更高的样本大小上，三分或更高的样本量。最后，我们进行仿真研究以显示我们提出的方法的优势并证实我们的理论发现。

We consider the nonlinear inverse problem of learning a transition operator $\mathbf{A}$ from partial observations at different times, in particular from sparse observations of entries of its powers $\mathbf{A},\mathbf{A}^2,\cdots,\mathbf{A}^{T}$. This Spatio-Temporal Transition Operator Recovery problem is motivated by the recent interest in learning time-varying graph signals that are driven by graph operators depending on the underlying graph topology. We address the nonlinearity of the problem by embedding it into a higher-dimensional space of suitable block-Hankel matrices, where it becomes a low-rank matrix completion problem, even if $\mathbf{A}$ is of full rank. For both a uniform and an adaptive random space-time sampling model, we quantify the recoverability of the transition operator via suitable measures of incoherence of these block-Hankel embedding matrices. For graph transition operators these measures of incoherence depend on the interplay between the dynamics and the graph topology. We develop a suitable non-convex iterative reweighted least squares (IRLS) algorithm, establish its quadratic local convergence, and show that, in optimal scenarios, no more than $\mathcal{O}(rn \log(nT))$ space-time samples are sufficient to ensure accurate recovery of a rank-$r$ operator $\mathbf{A}$ of size $n \times n$. This establishes that spatial samples can be substituted by a comparable number of space-time samples. We provide an efficient implementation of the proposed IRLS algorithm with space complexity of order $O(r n T)$ and per-iteration time complexity linear in $n$. Numerical experiments for transition operators based on several graph models confirm that the theoretical findings accurately track empirical phase transitions, and illustrate the applicability and scalability of the proposed algorithm.

Riemannian优化是解决优化问题的原则框架，其中所需的最佳被限制为光滑的歧管$ \ Mathcal {M} $。在此框架中设计的算法通常需要对歧管的几何描述，该描述通常包括切线空间，缩回和成本函数的梯度。但是，在许多情况下，由于缺乏信息或棘手的性能，只能访问这些元素的子集（或根本没有）。在本文中，我们提出了一种新颖的方法，可以在这种情况下执行近似Riemannian优化，其中约束歧管是$ \ r^{d} $的子手机。至少，我们的方法仅需要一组无噪用的成本函数$（\ x_ {i}，y_ {i}）\ in {\ mathcal {m}} \ times \ times \ times \ times \ times \ mathbb {r} $和内在的歧管$ \ MATHCAL {M} $的维度。使用样品，并利用歧管-MLS框架（Sober和Levin 2020），我们构建了缺少的组件的近似值，这些组件娱乐可证明的保证并分析其计算成本。如果某些组件通过分析给出（例如，如果成本函数及其梯度明确给出，或者可以计算切线空间），则可以轻松地适应该算法以使用准确的表达式而不是近似值。我们使用我们的方法分析了基于Riemannian梯度的方法的全球收敛性，并从经验上证明了该方法的强度，以及基于类似原理的共轭梯度类型方法。

最近，刘和张研究了从压缩传感的角度研究了时间序列预测的相当具有挑战性的问题。他们提出了一个没有学习的方法，名为卷积核规范最小化（CNNM），并证明了CNNM可以完全从其观察到的部分恢复一系列系列的部分，只要该系列是卷积的低级。虽然令人印象深刻，但是每当系列远离季节性时可能不满足卷积的低秩条件，并且实际上是脆弱的趋势和动态的存在。本文试图通过将学习，正常的转换集成到CNNM中，以便将一系列渐开线结构转换为卷积低等级的常规信号的目的。我们证明，由于系列的变换是卷积低级的转换，所以，所产生的模型是基于学习的基于学习的CNNM（LBCNM），严格成功地识别了一个系列的未来部分。为了学习可能符合所需成功条件的适当转换，我们设计了一种基于主成分追求（PCP）的可解释方法。配备了这种学习方法和一些精心设计的数据论证技巧，LBCNM不仅可以处理时间序列的主要组成部分（包括趋势，季节性和动态），还可以利用其他一些预测方法提供的预测;这意味着LBCNNM可以用作模型组合的一般工具。从时间序列数据库（TSDL）和M4竞争（M4）的100,452个现实世界时间序列的大量实验证明了LBCNNM的卓越性能。

This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the 1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.

我们为特殊神经网络架构，称为运营商复发性神经网络的理论分析，用于近似非线性函数，其输入是线性运算符。这些功能通常在解决方案算法中出现用于逆边值问题的问题。传统的神经网络将输入数据视为向量，因此它们没有有效地捕获与对应于这种逆问题中的数据的线性运算符相关联的乘法结构。因此，我们介绍一个类似标准的神经网络架构的新系列，但是输入数据在向量上乘法作用。由较小的算子出现在边界控制中的紧凑型操作员和波动方程的反边值问题分析，我们在网络中的选择权重矩阵中促进结构和稀疏性。在描述此架构后，我们研究其表示属性以及其近似属性。我们还表明，可以引入明确的正则化，其可以从所述逆问题的数学分析导出，并导致概括属性上的某些保证。我们观察到重量矩阵的稀疏性改善了概括估计。最后，我们讨论如何将运营商复发网络视为深度学习模拟，以确定诸如用于从边界测量的声波方程中重建所未知的WAVESTED的边界控制的算法算法。

随着科学和工程的越来越多的数据驱动，优化的作用已经扩展到几乎触及数据分析管道的每个阶段，从信号和数据获取到建模和预测。实践中遇到的优化问题通常是非convex。尽管挑战因问题而异，但非概念性的一个共同来源是数据或测量模型中的非线性。非线性模型通常表现出对称性，创建具有多种等效解决方案的复杂，非凸客观的景观。然而，简单的方法（例如，梯度下降）在实践中通常表现出色。这项调查的目的是突出一类可进行的非概念问题，可以通过对称性的镜头来理解。这些问题表现出特征性的几何结构：局部最小化是单个“地面真实”解决方案的对称副本，而其他关键点出现在地面真理的对称副本的平衡叠加上，并在破坏对称性的方向上表现出负曲率。该结构使有效的方法获得了全局最小化。我们讨论了由于成像，信号处理和数据分析中广泛的问题而引起的这种现象的示例。我们强调了对称性在塑造客观景观中的关键作用，并讨论旋转和离散对称性的不同作用。该区域充满了观察到的现象和开放问题。我们通过强调未来研究的方向结束。

本文从压缩感测的角度研究时间序列预测（TSF）的问题。首先，我们将TSF转换为具有任意采样（TCAS）的更加包容性问题，称为TCOR完成，该问题是从其条目的子集中以任意方式恢复张量。虽然已知在Tucker低级别的框架中，但理论上是不可能根据一些任意选择的条目识别目标张量，在这项工作中，我们将表明TCAS根据称为新概念的光明粘附卷积低秩，这是众所周知的傅立叶稀疏性的概括。然后我们介绍了一个凸面的卷积核规范最小化（CNNM），我们证明CNNM在求解TCA时，只要采样条件取决于目标张量的卷积等级 - 遵守。该理论为制作给定数量预测所需的最小采样大小提供了有意义的答案。单变量时间序列，图像和视频的实验显示令人鼓舞的结果。

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M . Can we complete the matrix and recover the entries that we have not seen?We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m ≥ C n 1.2 r log n for some positive numerical constant C, then with very high probability, most n × n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or N -way array. Decompositions of higher-order tensors (i.e., N -way arrays with N ≥ 3) have applications in psychometrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.

该博士学位论文的中心对象是在计算机科学和统计力学领域的不同名称中以不同名称而闻名的。在计算机科学中，它被称为“最大切割问题”，这是著名的21个KARP的原始NP硬性问题之一，而物理学的相同物体称为Ising Spin Glass模型。这种丰富的结构的模型通常是减少或重新制定计算机科学，物理和工程学的现实问题。但是，准确地求解此模型（查找最大剪切或基态）可能会留下一个棘手的问题（除非$ \ textit {p} = \ textit {np} $），并且需要为每一个开发临时启发式学特定的实例家庭。离散和连续优化之间的明亮而美丽的连接之一是一种基于半限定编程的圆形方案，以最大程度地切割。此过程使我们能够找到一个近乎最佳的解决方案。此外，该方法被认为是多项式时间中最好的。在本论文的前两章中，我们研究了旨在改善舍入方案的局部非凸照。在本文的最后一章中，我们迈出了一步，并旨在控制我们想要在前几章中解决的问题的解决方案。我们在Ising模型上制定了双层优化问题，在该模型中，我们希望尽可能少地调整交互作用，以使所得ISING模型的基态满足所需的标准。大流行建模出现了这种问题。我们表明，当相互作用是非负的时，我们的双层优化是在多项式时间内使用凸编程来解决的。

许多现代数据集，从神经影像和地统计数据等领域都以张量数据的随机样本的形式来说，这可以被理解为对光滑的多维随机功能的嘈杂观察。来自功能数据分析的大多数传统技术被维度的诅咒困扰，并且随着域的尺寸增加而迅速变得棘手。在本文中，我们提出了一种学习从多维功能数据样本的持续陈述的框架，这些功能是免受诅咒的几种表现形式的。这些表示由一组可分离的基函数构造，该函数被定义为最佳地适应数据。我们表明，通过仔细定义的数据的仔细定义的减少转换的张测仪分解可以有效地解决所得到的估计问题。使用基于差分运算符的惩罚，并入粗糙的正则化。也建立了相关的理论性质。在模拟研究中证明了我们对竞争方法的方法的优点。我们在神经影像动物中得出真正的数据应用。

网络数据通常在各种应用程序中收集，代表感兴趣的功能之间直接测量或统计上推断的连接。在越来越多的域中，这些网络会随着时间的流逝而收集，例如不同日子或多个主题之间的社交媒体平台用户之间的交互，例如在大脑连接性的多主体研究中。在分析多个大型网络时，降低降低技术通常用于将网络嵌入更易于处理的低维空间中。为此，我们通过专门的张量分解来开发用于网络集合的主组件分析（PCA）的框架，我们将半对称性张量PCA或SS-TPCA术语。我们得出计算有效的算法来计算我们提出的SS-TPCA分解，并在标准的低级别信号加噪声模型下建立方法的统计效率。值得注意的是，我们表明SS-TPCA具有与经典矩阵PCA相同的估计精度，并且与网络中顶点数的平方根成正比，而不是预期的边缘数。我们的框架继承了古典PCA的许多优势，适用于广泛的无监督学习任务，包括识别主要网络，隔离有意义的更改点或外出观察，以及表征最不同边缘的“可变性网络”。最后，我们证明了我们的提案对模拟数据的有效性以及经验法律研究的示例。用于建立我们主要一致性结果的技术令人惊讶地简单明了，可能会在其他各种网络分析问题中找到使用。

素描和项目是一个框架，它统一了许多已知的迭代方法来求解线性系统及其变体，并进一步扩展了非线性优化问题。它包括流行的方法，例如随机kaczmarz，坐标下降，凸优化的牛顿方法的变体等。在本文中，我们通过新的紧密频谱边界为预期的草图投影矩阵获得了素描和项目的收敛速率的敏锐保证。我们的估计值揭示了素描和项目的收敛率与另一个众所周知但看似无关的算法家族的近似误差之间的联系，这些算法使用草图加速了流行的矩阵因子化，例如QR和SVD。这种连接使我们更接近准确量化草图和项目求解器的性能如何取决于其草图大小。我们的分析不仅涵盖了高斯和次高斯的素描矩阵，还涵盖了一个有效的稀疏素描方法，称为较少的嵌入方法。我们的实验备份了理论，并证明即使极稀疏的草图在实践中也显示出相同的收敛属性。