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

BIGDATA：F：DKA：高维数据分析的随机方法

• 批准号: 1447471
• 负责人: Jelani Nelson
• 金额: $ 28.5万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1447471&HistoricalAwards=false
• 关键词: BIGDATA; DKA; Randomized; methods; dimensional

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.

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