Robust Computation of Linear Models, or How to Find a Needle in a Haystack

Abstract

Consider a dataset of vector-valued observations that consists of a modest number of noisy inliers, which are explained well by a low-dimensional subspace, along with a large number of outliers, which have no linear structure. This work describes a convex optimization problem, called reaper, that can reliably t a low-dimensional model to this type of data. The paper provides an efficient algorithm for solving the reaper problem, and it documents numerical experiments which confirm that reaper can dependably nd linear structure in synthetic and natural data. In addition, when the inliers are contained in a low-dimensional subspace, there is a rigorous theory that describes when reaper can recover the subspace exactly.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 17, 2012
Accession Number
ADA563093

Entities

People

  • Gilad Lerman
  • Joel A. Tropp
  • Michael Mccoy
  • Teng Zhang

Organizations

  • California Institute of Technology

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computations
  • Data Mining
  • Databases
  • Dimensionality Reduction
  • Factor Analysis
  • Geometry
  • Information Processing
  • Information Retrieval
  • Information Science
  • Machine Learning
  • Mathematics
  • Network Science
  • Optimization
  • Probability
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Distributed Systems and Data Platform Development
  • Linear Algebra
  • Neural Network Machine Learning.