本文缩小了先前有关量子线性代数的文献与量子计算机上的实用数据分析之间的差异，从而使量子程序形式化，以加快机器学习中数据表示的本本本特征的解决方案。这些子例程的功率和实际用途通过新的量子算法（输入矩阵的大小中的sublinear）显示，用于主成分分析，通信分析和潜在的语义分析。我们提供了对运行时的理论分析，并在随机算法的误差上证明了紧密的界限。我们在多个数据集上运行实验，以模拟PCA的尺寸减小，以通过新型例程进行图像分类。结果表明，不依赖输入的大小的运行时参数是合理的，并且计算模型上的错误很小，从而允许竞争性分类性能。

我们提出了一个算法框架，用于近距离矩阵上的量子启发的经典算法，概括了Tang的突破性量子启发算法开始的一系列结果，用于推荐系统[STOC'19]。由量子线性代数算法和gily \'en，su，low和wiebe [stoc'19]的量子奇异值转换（SVT）框架[SVT）的动机[STOC'19]，我们开发了SVT的经典算法合适的量子启发的采样假设。我们的结果提供了令人信服的证据，表明在相应的QRAM数据结构输入模型中，量子SVT不会产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术，因此我们的结果与先前工作的采样引理相结合，足以概括所有有关取消量子机器学习算法的最新结果。特别是，我们的经典SVT框架恢复并经常改善推荐系统，主成分分析，监督聚类，支持向量机器，低秩回归和半决赛程序解决方案的取消结果。我们还为汉密尔顿低级模拟和判别分析提供了其他取消化结果。我们的改进来自识别量子启发的输入模型的关键功能，该模型是所有先前量子启发的结果的核心：$ \ ell^2 $ -Norm采样可以及时近似于其尺寸近似矩阵产品。我们将所有主要结果减少到这一事实，使我们的简洁，独立和直观。

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.

量子计算有可能彻底改变和改变我们的生活和理解世界的方式。该审查旨在提供对量子计算的可访问介绍，重点是统计和数据分析中的应用。我们从介绍了了解量子计算所需的基本概念以及量子和经典计算之间的差异。我们描述了用作量子算法的构建块的核心量子子程序。然后，我们审查了一系列预期的量子算法，以便在统计和机器学习中提供计算优势。我们突出了将量子计算应用于统计问题的挑战和机遇，并讨论潜在的未来研究方向。

即使在数十年的量子计算开发之后，通常在经典同行中具有指数加速的通常有用量子算法的示例是稀缺的。线性代数定位量子机学习（QML）的量子算法中的最新进展作为这种有用的指数改进的潜在来源。然而，在一个意想不到的发展中，最近一系列的“追逐化”结果同样迅速消除了几个QML算法的指数加速度的承诺。这提出了关键问题是否是其他线性代数QML算法的指数加速度持续存在。在本文中，我们通过该镜头研究了Lloyd，Garnerone和Zanardi的拓扑数据分析算法后面的量子算法方法。我们提供了证据表明，该算法解决的问题通过表明其自然概括与模拟一个清洁量子位模型很难地难以进行棘手的 - 这被广泛认为需要在经典计算机上需要超时时间 - 并且非常可能免疫追逐。基于此结果，我们为等级估计和复杂网络分析等问题提供了许多新的量子算法，以及其经典侵害性的复杂性 - 理论上。此外，我们分析了近期实现的所提出的量子算法的适用性。我们的结果为全面吹嘘和限制的量子计算机提供了许多有用的应用程序，具有古典方法的保证指数加速，恢复了线性代数QML的一些潜力，以成为量子计算的杀手应用之一。

我们研究基于Krylov子空间的迭代方法，用于在任何Schatten $ p $ Norm中的低级别近似值。在这里，通过矩阵向量产品访问矩阵$ a $ $如此$ \ | a（i -zz^\ top）\ | _ {s_p} \ leq（1+ \ epsilon）\ min_ {u^\ top u = i_k} } $，其中$ \ | m \ | _ {s_p} $表示$ m $的单数值的$ \ ell_p $ norm。对于$ p = 2 $（frobenius norm）和$ p = \ infty $（频谱规范）的特殊情况，musco and Musco（Neurips 2015）获得了基于Krylov方法的算法，该方法使用$ \ tilde {o}（k）（k /\ sqrt {\ epsilon}）$ matrix-vector产品，改进na \“ ive $ \ tilde {o}（k/\ epsilon）$依赖性，可以通过功率方法获得，其中$ \ tilde {o} $抑制均可抑制poly $（\ log（dk/\ epsilon））$。我们的主要结果是仅使用$ \ tilde {o}（kp^{1/6}/\ epsilon^{1/3} {1/3}）$ matrix $ matrix的算法 - 矢量产品，并为所有$ p \ geq 1 $。为$ p = 2 $工作，我们的限制改进了先前的$ \ tilde {o}（k/\ epsilon^{1/2}）$绑定到$ \ tilde {o}（k/\ epsilon^{1/3}）$。由于schatten- $ p $和schatten-$ \ infty $ norms在$（1+ \ epsilon）$ pers $ p时相同\ geq（\ log d）/\ epsilon $，我们的界限恢复了Musco和Musco的结果，以$ p = \ infty $。此外，我们证明了矩阵矢量查询$ \ omega的下限（1/\ epsilon^ {1/3}）$对于任何固定常数$ p \ geq 1 $，表明令人惊讶的$ \ tilde {\ theta}（1/\ epsilon^{ 1/3}）$是常数〜$ k $的最佳复杂性。为了获得我们的结果，我们介绍了几种新技术，包括同时对多个Krylov子空间进行优化，以及针对分区操作员的不平等现象。我们在[1,2] $中以$ p \的限制使用了Araki-lieb-thirring Trace不平等，而对于$ p> 2 $，我们呼吁对安装分区操作员的规范压缩不平等。

我们创建经典的（非量词）动态数据结构，为推荐系统和最小二乘回归的查询提供了与量子类似物相当的查询。近年来，这种算法的去量化引起了人们的关注。我们为这些问题获得了更清晰的界限。更重要的是，我们通过争辩说，这些问题的先前量子启发算法正在做杠杆或脊杠杆得分取样，以实现这些改进。这些是随机数值线性代数中强大而标准的技术。有了这种识别，我们能够在数值线性代数中采用大量工作来获得这些问题的算法，这些算法比现有方法更简单或更快（或两者兼而有之）。我们的实验表明，所提出的数据结构在现实世界数据集上也很好地工作。

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

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.

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

The Forster transform is a method of regularizing a dataset by placing it in {\em radial isotropic position} while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given {\em weakly} polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first {\em strongly polynomial time} algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for {\em distribution-free} PAC learning of halfspaces. This learning result is surprising because {\em proper} PAC learning of halfspaces is {\em equivalent} to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

我们提出了第一近最优量子算法，用于估计欧几里德的规范，与有限均值和协方差的矢量值随机变量的平均值。我们的结果旨在将多元子高斯估计的理论延伸到量子设置。与经典上不同，如果任何单变量估计器都可以在维度中最多的对数开销转换为多变量估计器，则不会在量子设置中证明类似的结果。实际上，当样品复杂性小于尺寸时，Heinrich排除了平均估计问题的量子优势。我们的主要结果是表明，在这种低精度的方案之外，有一个量子估计值优于任何经典估算器。我们的方法比单变量设置大致涉及，大多数量子估计人员依赖于相位估计。我们利用各种额外的算法技术，如幅度放大，伯恩斯坦 - Vazirani算法和量子奇异值转换。我们的分析还使用多元截断统计的浓度不等式。我们以前在文献中出现的两个不同输入模型中的Quantum估算器。第一个提供对随机变量的二进制表示的相干访问，并且它包含经典设置。在第二模型中，随机变量直接编码到量子寄存器的相位中。该模型在许多量子算法中自然出现，但常常具有古典样品通常是无与伦比的。我们将我们的技术调整为这两个设置，我们表明第二种模型严格较弱，以解决平均估计问题。最后，我们描述了我们的算法的几个应用，特别是在测量通勤可观察到的期望值和机器学习领域时。

NYSTR \“ OM方法是提高内核方法可伸缩性的最流行技术之一。但是，它尚未与经典PCA一致的核PCA得出。在本文中，我们使用NyStr \”来得出核PCA。OM方法，从而提供了使内核PCA可扩展的少数可用选项之一。我们通过与完整方法相比，通过有限样本的置信度结合了经验重建误差，进一步研究其统计精度。该方法和绑定的行为通过在多个现实世界数据集上的计算机实验进行说明。作为该方法的应用，我们使用NyStr \“ Om方法表示内核主成分回归，作为NyStr \“ Om内核脊回归的替代方案，可用于使用核有效正规化回归。

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.

量子计算为某些问题提供了指数加速的潜力。但是，许多具有可证明加速的现有算法都需要当前不可用的耐故障量子计算机。我们提出了NISQ-TDA，这是第一个完全实现的量子机学习算法，其在任意经典（非手动）数据上具有可证明的指数加速，并且仅需要线性电路深度。我们报告了我们的NISQ-TDA算法的成功执行，该算法应用于在量子计算设备以及嘈杂的量子模拟器上运行的小数据集。我们从经验上证实，该算法对噪声是可靠的，并提供了目标深度和噪声水平，以实现现实世界中问题的近期，无耐受耐受性的量子优势。我们独特的数据加载投影方法是噪声鲁棒性的主要来源，引入了一种新的自我校正数据加载方法。

求解线性系统的迭代方法的收敛速率$ \ mathbf {a} x = b $通常取决于矩阵$ \ mathbf {a} $的条件号。预处理是通过以计算廉价的方式减少该条件号来加速这些方法的常用方式。在本文中，我们通过左或右对角线重构重新审视如何最好地提高$ \ mathbf {a}条件号的数十年。我们在几个方向上取得了这个问题。首先，我们为缩放$ \ mathbf {a} $的经典启发式提供了新的界限（a.k.a.jacobi预处理）。我们证明了这种方法将$ \ MATHBF {a} $的条件号减少到最佳可能缩放的二次因素中。其次，我们为结构化混合包装和覆盖了Semidefinite程序（MPC SDP）提供了一个求解器，它计算$ \ mathbf {a} $ in $ \ widetilde {o}（\ text {nnz}（\ mathbf {a}）\ cdot \ text {poly}（\ kappa ^ \ star））$ time;这与在缩放到$ \ widetilde {o}（\ text {poly}（\ kappa ^ \ star））$ factors之后求解线性系统的成本匹配。第三，我们证明了足够一般的宽度无关的MPC SDP求解器将暗示我们考虑的缩放问题的近乎最佳的运行时间，以及与平均调理措施有关的自然变体。最后，我们突出了我们的预处理技术与半随机噪声模型的连接，以及在几种统计回归模型中降低风险的应用。

Tensor完成是矩阵完成的自然高阶泛化，其中目标是从其条目的稀疏观察中恢复低级张量。现有算法在没有可证明的担保的情况下是启发式，基于解决运行不切实际的大型半纤维程序，或者需要强大的假设，例如需要因素几乎正交。在本文中，我们介绍了交替最小化的新变型，其又通过了解如何对矩阵设置中的交替最小化的收敛性的进展措施来调整到张量设置的启发。我们展示了强大的可证明的保证，包括表明我们的算法即使当因素高度相关时，我们的算法也会在真正的张量线上会聚，并且可以在几乎线性的时间内实现。此外，我们的算法也非常实用，我们表明我们可以完成具有千维尺寸的三阶张量，从观察其条目的微小一部分。相比之下，有些令人惊讶的是，我们表明，如果没有我们的新扭曲，则表明交替最小化的标准版本可以在实践中以急剧速度收敛。

分类属性是那些可以采用离散值集的那些，例如颜色。这项工作是关于将vects压缩到基于小维度离散矢量的分类属性。基于目前的哈希的方法将传感器压缩到低维离散矢量的分类属性不提供压缩表示之间的汉明距离的任何保证。在这里，我们呈现fsketch以创建稀疏分类数据的草图和估算器，以估计仅从其草图中的未压缩数据之间的成对汉明距离。我们声称这些草图可以在通常的数据挖掘任务中使用代替原始数据而不会影响任务的质量。为此，我们确保草图也是分类，稀疏，汉明距离估计是合理的精确性。素描结构和汉明距离估计算法都只需要一条单通;此外，对数据点的改变可以以有效的方式结合到其草图中。压缩性取决于数据的稀疏程度如何且与原始维度无关 - 使我们的算法对许多现实生活场景具有吸引力。我们的索赔通过对FSKetch性质的严格理论分析来支持，并通过对某些现实世界数据集的相关算法进行广泛的比较评估。我们表明FSKetch明显更快，并且通过使用其草图获得的准确性是RMSE，聚类和相似性搜索的标准无监督任务的顶部。

我们研究了用于线性回归的主动采样算法，该算法仅旨在查询目标向量$ b \ in \ mathbb {r} ^ n $的少量条目，并将近最低限度输出到$ \ min_ {x \ In \ mathbb {r} ^ d} \ | ax-b \ | $，其中$ a \ in \ mathbb {r} ^ {n \ times d} $是一个设计矩阵和$ \ | \ cdot \ | $是一些损失函数。对于$ \ ell_p $ norm回归的任何$ 0 <p <\ idty $，我们提供了一种基于Lewis权重采样的算法，其使用只需$ \ tilde {o}输出$（1+ \ epsilon）$近似解决方案（d ^ {\ max（1，{p / 2}）} / \ mathrm {poly}（\ epsilon））$查询到$ b $。我们表明，这一依赖于$ D $是最佳的，直到对数因素。我们的结果解决了陈和Derezi的最近开放问题，陈和Derezi \'{n} Ski，他们为$ \ ell_1 $ norm提供了附近的最佳界限，以及$ p \中的$ \ ell_p $回归的次优界限（1,2） $。我们还提供了$ O的第一个总灵敏度上限（D ^ {\ max \ {1，p / 2 \} \ log ^ 2 n）$以满足最多的$ p $多项式增长。这改善了Tukan，Maalouf和Feldman的最新结果。通过将此与我们的技术组合起来的$ \ ell_p $回归结果，我们获得了一个使$ \ tilde o的活动回归算法（d ^ {1+ \ max \ {1，p / 2 \}} / \ mathrm {poly}。 （\ epsilon））$疑问，回答陈和德里兹的另一个打开问题{n}滑雪。对于Huber损失的重要特殊情况，我们进一步改善了我们对$ \ tilde o的主动样本复杂性的绑定（d ^ {（1+ \ sqrt2）/ 2} / \ epsilon ^ c）$和非活跃$ \ tilde o的样本复杂性（d ^ {4-2 \ sqrt 2} / \ epsilon ^ c）$，由于克拉克森和伍德拉夫而改善了Huber回归的以前的D ^ 4 $。我们的敏感性界限具有进一步的影响，使用灵敏度采样改善了各种先前的结果，包括orlicz规范子空间嵌入和鲁棒子空间近似。最后，我们的主动采样结果为每种$ \ ell_p $ norm提供的第一个Sublinear时间算法。

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples.