CAREER: Transforming data analysis via new algorithms for feature extraction

分析和探索数据，包括分类、推理和检索，是科学和应用领域中普遍存在的任务。对于任何这样的任务，一个基本的范例是提取相关的特征。在设计用于分析和探索数据的算法时，特征提取技术充当基本的构建块或基元，可以组合起来对复杂行为进行建模。一些基本的特征提取工具包括主成分分析(PCA)、独立成分分析(ICA)和基于半空间的学习和分类。数据很少满足这些模型和特征提取工具的精确假设，而组合这些工具会放大误差。本文的工作将：(1)将独立分量分析从一个非常成功的实用工具提升为算法原语，具有很强的理论保证和对除独立之外的一类丰富问题的适用性。(2)找到合理的假设和算法，允许高效地学习半空间的交集。(3)系统地研究称为子集选择问题的主元分析的下列动机良好的求精方法。新的特征提取算法增强了生物学、信号处理和计算机视觉等数据密集型领域的研究人员可用的工具箱。它们还使安全、营销、商业和政府流程的从业者能够改进数据分析，基本上在任何涉及功能丰富的数据分析的领域都是如此。这个项目的教育和推广方面包括对年轻研究人员的指导，为研究生和本科生设计一门新课程，将PI的一些研究纳入其中，以及让大学预科学生和当地社区参与科学和研究。

Analysis and exploration of data, including classification, inference, and retrieval, are ubiquitous tasks in science and applied fields. Given any such task, a fundamental paradigm is the extraction of features that are relevant. In the design of algorithms for the analysis and exploration of data, feature extraction techniques act as basic building blocks or primitives that can be combined to model complex behavior. Some of the fundamental feature extraction tools include Principal Component Analysis (PCA), Independent Component Analysis (ICA), and half-space-based learning and classification. Data rarely satisfy the precise assumptions of these models and feature extraction tools, and combining these tools amplifies errors. This motivates the challenging task of designing new algorithms that are robust against noise and that can be combined as building blocks while keeping the error propagation under control.The proposed work will:(1) Raise ICA from a very successful practical tool to an algorithmic primitive with strong theoretical guarantees and applicability to a rich family of problems beyond independence.(2) Find reasonable assumptions and algorithms that allow efficient learning of intersections of half-spaces.(3) Systematically study the following well-motivated refinement of PCA known as the subset selection problem. This refinement aims to select relevant features among the given features of the input data, unlike PCA, which creates new and possibly artificial features.New feature extraction algorithms enhance the toolbox available to researchers in data-intensive fields such as biology, signal processing and computer vision. They also enable improved data analysis by practitioners in security, marketing, business and government processes, and essentially any field that involves the analysis of feature-rich data. The proposed work includes the implementation of the more practical algorithms.Education and outreach aspects of this project include the mentoring of young researchers, the design of a new course for graduate and undergraduate students incorporating some of the PI's research, and the involvement of pre-college students and local communities into science and research.