III: Medium: Non-Convex Methods for Discovering High-Dimensional Structures in Big and Corrupted Data

III：媒介：在大数据和损坏数据中发现高维结构的非凸方法

基本信息

批准号：
1704458
负责人：
Rene Vidal
金额：
$ 115万
依托单位：
Johns Hopkins University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-08-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1704458&HistoricalAwards=false
关键词：
III Medium Non Convex Methods

项目摘要

Discovering structure in high-dimensional data, such as images, videos and 3D point clouds, has become an essential part of scientific discovery in many disciplines, including machine learning, computer vision, pattern recognition, and signal processing. This has motivated extraordinary advances in the past decade, including various sparse and low-rank modeling methods based on convex optimization with provable theoretical guarantees of correct recovery. However, existing theory and algorithms rely on the assumption that high-dimensional data can be well approximated by low-dimensional structures. While this assumption is adequate for some datasets, e.g., images of faces under varying illumination, it may be violated in many emerging datasets, e.g., 3D point clouds. The goal of this project is to develop a mathematical modeling framework and associated non-convex optimization tools for discovering high-dimensional structures in big and corrupted data.This project will develop provably correct and scalable optimization algorithms for learning a union of high-dimensional subspaces from big and corrupted data. The proposed algorithms will be based on a novel framework called Dual Principal Component Pursuit that, instead of learning a basis for each subspace, seeks to learn a basis for their orthogonal complements. In sharp contrast with existing sparse and low-rank methods, which require both the dimensions of the subspaces and the percentage of outliers to be sufficiently small, the proposed framework will lead to results where even subspaces of the highest possible dimension (i.e., hyperplanes) can be correctly recovered from highly corrupted data. This will be achieved by solving a family of non-convex sparse representation problems whose analysis will require the development of novel theoretical results to guarantee the correct recovery of the subspaces from corrupted data. The project will also develop scalable algorithms for solving these non-convex optimization problems and study conditions for their convergence to the global optimum. These algorithms will be evaluated in two major applications in computer vision: segmentation of point clouds and clustering of image categorization datasets.

发现图像、视频和 3D 点云等高维数据中的结构已成为许多学科（包括机器学习、计算机视觉、模式识别和信号处理）科学发现的重要组成部分。这在过去十年中推动了非凡的进步，包括基于凸优化的各种稀疏和低秩建模方法，并具有可证明的正确恢复的理论保证。然而，现有的理论和算法依赖于高维数据可以很好地用低维结构来近似的假设。虽然这种假设对于某些数据集来说是足够的，例如不同光照下的人脸图像，但在许多新兴数据集（例如 3D 点云）中可能会违反这一假设。该项目的目标是开发一个数学建模框架和相关的非凸优化工具，用于发现大数据和损坏数据中的高维结构。该项目将开发可证明正确且可扩展的优化算法，用于学习高维子空间的并集来自大数据和损坏的数据。所提出的算法将基于一种称为“双主成分追踪”的新颖框架，该框架不是学习每个子空间的基础，而是寻求学习其正交补集的基础。与现有的稀疏和低秩方法形成鲜明对比，现有的稀疏和低秩方法要求子空间的维度和异常值的百分比都足够小，所提出的框架将导致即使是最高可能维度的子空间（即超平面）的结果可以从高度损坏的数据中正确恢复。这将通过解决一系列非凸稀疏表示问题来实现，这些问题的分析需要开发新颖的理论结果，以保证从损坏的数据中正确恢复子空间。该项目还将开发可扩展的算法来解决这些非凸优化问题，并研究它们收敛到全局最优的条件。这些算法将在计算机视觉的两个主要应用中进行评估：点云分割和图像分类数据集聚类。

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis

低秩子空间聚类的非凸公式：算法和收敛性分析

DOI：
10.1007/s10589-018-0002-6
发表时间：
2018-03-27
期刊：
Computational Optimization and Applications
影响因子：
2.2
作者：
Hao Jiang;Daniel P. Robinson;R. Vidal;Chong You
通讯作者：
Chong You

A novel variational form of the Schatten-p quasi-norm

Schatten-p 拟范数的一种新颖变分形式

DOI：
发表时间：
2020-10-26
期刊：
ArXiv
影响因子：
0
作者：
Paris V. Giampouras;R. Vidal;A. Rontogiannis;B. Haeffele
通讯作者：
B. Haeffele

A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis

低秩子空间聚类的非凸公式：算法和收敛性分析

DOI：
发表时间：
2018-04
期刊：
Computational optimization and applications
影响因子：
2.2
作者：
Jiang, Hao;Robinson, Daniel P.;Vidal, Rene;You, Chong
通讯作者：
You, Chong

A Critique of Self-Expressive Deep Subspace Clustering

对自我表达深层子空间聚类的批判

DOI：
发表时间：
2020-10-08
期刊：
ArXiv
影响因子：
0
作者：
B. Haeffele;Chong You;R. Vidal
通讯作者：
R. Vidal

The fastest L1,oo prox in the west

西方最快的L1,oo prox

DOI：
10.1109/tpami.2021.3059301
发表时间：
2021-02
期刊：
IEEE Transactions on Pattern Analysis and Machine Intelligence
影响因子：
23.6
作者：
Bejar, Benjamin;Dokmanic, Ivan;Vidal, Rene
通讯作者：
Vidal, Rene

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

Rene Vidal其他文献

A Structured Sparse Plus Structured Low-Rank Framework for Subspace Clustering and Completion

用于子空间聚类和补全的结构化稀疏加结构化低秩框架

DOI：
10.1109/tsp.2016.2613070
发表时间：
2016
期刊：
IEEE Transactions on Signal Processing
影响因子：
5.4
作者：
Chun-Guang Li;Rene Vidal
通讯作者：
Rene Vidal

Clustering-based Domain-Incremental Learning

基于聚类的领域增量学习

DOI：
10.1109/iccvw60793.2023.00363
发表时间：
2023-09-21
期刊：
2023 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW)
影响因子：
0
作者：
Christiaan Lamers;Rene Vidal;A. Belbachir;N. V. Stein;Thomas Bäck;Paris Giampouras
通讯作者：
Paris Giampouras