BIGDATA: F: DKA: Randomized methods for high-dimensional data analysis

随机化方法最近被证明在有效分析大数据集方面非常有用，该项目涵盖了用于开发此类算法以有效分析和存储此类数据的数学严格技术。特别是这个项目的重点是进一步应用最近的随机化方法的大规模计算线性代数。这项研究的应用包括：随机线性代数，流形学习和基于模型的压缩感知。在这些领域的问题上，许多已开发的技术都是通过随机化的“不经意子空间嵌入”这一共同工具来统一的。“这项研究解决了随机线性代数、流形学习和基于模型的压缩感知中的大数据问题。在随机线性代数中，假设输入是一个非常大的矩阵A，目标是有效地处理这个输入，例如，以回归、主成分分析、（近似）矩阵乘法、特征值估计、k均值聚类等的形式。Sarlos首先提出的是使用“不经意子空间嵌入”来加速计算的想法，即，（从适当的分布中）挑选随机矩阵S，使得在SA而不是A上解决问题仍然产生原始问题的几乎最优的解决方案（其中选择S使得SA具有比A少得多的行，从而压缩大量数据）。该项目开发了新的方法来获得更有效的S，以及找到新的应用核化和正则化回归问题。在流形学习中，人们想象输入数据位于高维空间中的低维流形上。例如，像素化的手写图像可以被视为高维向量（由像素索引），而根据经验，已经观察到这样的图像倾向于位于低得多的维度流形附近。通过学习这些参数（“流形学习”），可以进行更有效的分类器训练并实现数据压缩。这个项目探索了更有效的方法来使用随机方法进行流形学习，例如，通过使用有效的子空间嵌入。在基于模型的压缩感知中，人们希望使用很少的线性测量来有效地获取具有结构化稀疏模式的稀疏信号，以用于稍后的（近似）恢复。将这些测量组织为测量矩阵S的行，已知这样的S与子空间嵌入紧密相连。本项目旨在探索这种联系，以获得更有效的基于模型的压缩感知和恢复算法。

Randomized methods have recently proven highly useful in efficiently analyzing big data sets, and this project covers mathematically rigorous techniques for developing such algorithms to analyze and store such data efficiently. In particular this project focuses on furthering applications of recent randomized methods for large-scale computational linear algebra. Applications of this research include: randomized linear algebra, manifold learning, and model-based compressed sensing. Many of the developed technologies on problems in these areas are unified by the common tool of randomized "oblivious subspace embeddings."This research attacks the big data problem in randomized linear algebra, manifold learning, and model-based compressed sensing. In randomized linear algebra one imagines that the input is an extremely large matrix A, and the goal is to efficiently process this input, e.g., in the form of regression, principal component analysis, (approximate) matrix multiplication, eigenvalue estimation, k-means clustering, etc. First proposed by Sarlos was the idea of using "oblivious subspace embeddings" to speed up computation, i.e., picking a random matrix S (from an appropriate distribution) such that solving the problem on SA instead of A still yields an almost optimal solution to the original problem (where S is chosen so that SA has many fewer rows than A, thus compressing the massive data). This project develops novel methods to obtain more efficient such S, as well as to find new applications to kernelized and regularized regression problems.In manifold learning one imagines that the input data lies on a low-dimensional manifold in a high-dimensional space. For example, pixelated handwritten images can be viewed as high-dimensional vectors (indexed by pixels), whereas empirically it has been observed that such images tend to lie near a much lower dimensional manifold. By learning these parameters ("manifold learning"), one can do more efficient classifier training as well as achieve data compression. This project explores more efficient ways to use randomized methods to do manifold learning, e.g., by using efficient subspace embeddings. In model-based compressed sensing one wishes to acquire sparse signals with structured sparsity patterns efficiently using few linear measurements, for later (approximate) recovery. Organizing these measurements as the rows of a measurement matrix S, it is known that such S are closely connected to subspace embeddings. This project aims to explore this connection to obtain more efficient model-based compressed sensing and recovery algorithms.