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

相机拍摄的图像是一个数字矩阵，但大多数数字矩阵看起来都不像图像——图像中的数字矩阵反映了场景的结构。科学、工程和商业领域的数据分析的许多应用可以看作是采用观察矩阵并拟合低秩或其他结构化矩阵来解释它们之间的关系。图像和视频分析并不是唯一的例子；这个问题出现在社交网络的结构分析、预测用户对新产品和服务的偏好以及许多其他分析任务中。随着这些问题的规模和维度的增加，数据分析师面临着严谨性和规模之间的差距：理论上合理的算法通常具有仅在中等规模的数据集上可行的要求（例如重复/随机访问数据），即使这样，也可能无法在“交互时间”（即人类交互式分析数据所需的较小时间尺度）内提供答案。因此，实践转向了缺乏严格保证的方法，但这些方法是可伸缩的，并且已被观察到可以提供适当的近似。该项目旨在通过两项技术观察来缩小这一差距：(a)认识到快速矩阵推理需要非凸算法，它专注于开发对该算法的严格分析，以及(b)在算法设计和统计分析阶段本身明确地结合大数据架构（非核心和分布式多核）。它侧重于几个特定的任务，包括通过有效的低秩近似，最小化低秩矩阵的非凸集上的一般凸函数，鲁棒矩阵估计以及非线性和核矩阵设置。该项目培养研究生的数学和计算发展对数据分析很重要。大数据的前景只能通过扩展数据基础设施来实现，以继续提供统计上有意义的见解；本项目旨在实现这一承诺的一大套矩阵估计问题。

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.