Robust computation of linear models by convex relaxation
Consider a dataset of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a convex optimization problem, called REAPER, that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors, and it uses a relaxation of the set of orthogonal projectors to reach the convex formulation. The paper provides an efficient algorithm for solving the REAPER problem, and it documents numerical experiments which confirm that REAPER can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when REAPER can approximate this subspace.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Statistical Limits of Convex Relaxations
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite pro…
Sparse LearningStochastic Block ModelThe Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike previous single-neuron relaxations which f…
Convex mixed-integer optimization with Frank-Wolfe methods
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound a…
Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations
The non-convex nature of trained neural networks has created significant obstacles in their incorporation into optimization models. Considering the wide array of applications that this embedding has, the optimization and…
Policy Relevant Treatment Effects with Multidimensional Unobserved Heterogeneity
This paper provides a unified framework for bounding policy relevant treatment effects using instrumental variables. In this framework, the treatment selection may depend on multidimensional unobserved heterogeneity. We …
Informativeness