Abstract: We consider the problem of learning a union of subspaces from data corrupted by outliers. State-of-the-art methods based on convex l1 and nuclear norm minimization require the subspace dimensions and the number of outliers to be sufficiently small. In this talk I will present a non-convex approach called Dual Principal Component Pursuit (DPCP), which can provably learn subspaces of high relative dimension and tolerate a large number of outliers by solving a non-convex l1 minimization problem on the sphere. Specifically, I will present both geometric and probabilistic conditions under which every global solution to the DPCP problem is a vector in the orthogonal complement to one of the subspaces. Such conditions show that DPCP can tolerate as many outliers as the square of the number of inliers. I will also present various optimization algorithms for solving the DPCP problem and show that a Projected Sub-Gradient Method admits linear convergence to the global minimum of the underlying non-convex and non-smooth optimization problem. Experiments show that the proposed method is able to handle more outliers and higher relative dimensions than state-of-the-art methods. Joint work with Tianjiao Ding, Daniel Robinson, Manolis Tsakiris and Zhihui Zhu.
Biosketch: René Vidal is the Herschel Seder Professor of Biomedical Engineering and Director of the Mathematical Institute for Data Science at Johns Hopkins University. He is also an Amazon Scholar, Chief Scientist at NORCE, and Associate Editor in Chief of TPAMI. He also directs the NSF-Simons Collaboration on the Mathematical Foundations of Deep Learning and the TRIPODS Institute on the Foundations of Graph and Deep Learning. His current research focuses on the foundations of deep learning and its applications in computer vision and biomedical data science. He is an AIMBE Fellow, IEEE Fellow, IAPR Fellow and Sloan Fellow, and has received numerous awards for his work, including the IEEE Edward J. McCluskey Technical Achievement Award, D’Alembert Faculty Award, J.K. Aggarwal Prize, ONR Young Investigator Award, NSF CAREER Award as well as best paper awards in machine learning, computer vision, controls, and medical robotics.