AF: Medium: Dropping Convexity: New Algorithms, Statistical Guarantees and Scalable Software for Non-convex Matrix Estimation

AF：中：降低凸性：用于非凸矩阵估计的新算法、统计保证和可扩展软件

• 批准号: 1564000
• 负责人: Sujay Sanghavi
• 金额: $ 90.24万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1564000&HistoricalAwards=false
• 关键词: AF; Medium; Dropping; Convexity; New

An image from your camera is a matrix of numbers, but most matrices of numbers would not look like an image -- the matrix of numbers in an image reflect structure from the scene. Many applications of data analysis across science, engineering, and business can be viewed as taking a matrix of observations and fitting low-rank or otherwise structured matrices to explain their relationships. Image and video analysis is not the only example; the problem arises in structural analysis of social networks, divining user preferences for new products and services, and many other analysis tasks. As the scale and dimensionality of these problems increases, the data analyst is faced with a gap between rigor and scale: theoretically sound algorithms often have requirements (e.g. repeated/random access to data) that are feasible only on medium-scale datasets, and even then may not provide answers in "interactive time" (i.e. smallish time scales required for a human interactively analyzing data). Thus practice has turned towards methods that lack rigorous guarantees, but that are scalable and have been observed to provide decent approximation. This project aims to narrow this gap by two technical observations: (a) Recognizing that fast matrix inference necessitates non-convex algorithms, it focuses on developing a rigorous analysis of the same, and (b) by explicitly incorporating big-data architectures (out of core, and distributed multicore) in the algorithm design and statistical analysis stage itself. it focuses on several specific tasks, including pass-efficient low-rank approximation, minimizing general convex functions over the non-convex set of low-rank matrices, robust matrix estimation, and non-linear and kernel matrix settings. The project trains graduate students in the mathematical and computational development important for data analysis. The promise of big data can only be realized by scaling infrastructure with data to continue to provide statistically meaningful insights; this project aims to realize this promise for a large suite of matrix estimation problems.

来自相机的图像是数字的矩阵，但是大多数数字矩阵看起来不像图像 - 图像中数字的矩阵反映了场景的结构。 跨科学，工程和业务的数据分析的许多应用都可以看作是对观测值进行矩阵，并适合低级或其他结构化的矩阵来解释其关系。图像和视频分析不是唯一的例子。问题出现在社交网络的结构分析，对新产品和服务的用户偏好以及许多其他分析任务中产生。随着这些问题的规模和维度的增加，数据分析师面临严格和规模之间的差距：从理论上讲，声音算法通常具有仅在中等规模数据集上可行的要求（例如，重复/随机访问数据），即使那样，甚至可能在“交互时间”中提供“互动时间”的答案（即，smillish time scales scales scales scales scales scales cretments totals互动分析都需要数据分析）。因此，实践转向缺乏严格保证的方法，但可以扩展并被观察到提供体面的近似值。该项目的目的是通过两个技术观察结果来缩小这一差距：（a）认识到快速矩阵推理需要非convex算法，它着重于对同一的严格分析进行严格的分析，以及（b）通过在Algorithm Designistics Analless和统计分析阶段中明确结合Big-Data架构（核心和分布式多核）。它着重于几个特定的​​任务，包括传递效率低级别近似，最大程度地降低了非凸点的一般凸函数，低级别矩阵，可靠的矩阵估计以及非线性和内核矩阵设置。该项目培训了数学和计算发展的研究生对于数据分析很重要。大数据的承诺只能通过使用数据扩展基础架构来继续提供统计意义的见解来实现。该项目旨在实现这一诺言，以实现大量矩阵估计问题。