A Caltech Library Service

Robust Computation of Linear Models by Convex Relaxation

Lerman, Gilad and McCoy, Michael B. and Tropp, Joel A. and Zhang, Teng (2015) Robust Computation of Linear Models by Convex Relaxation. Foundations of Computational Mathematics, 15 (2). pp. 363-410. ISSN 1615-3375.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Consider a data set 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 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 that 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.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle Paper ReadCube access
Tropp, Joel A.0000-0003-1024-1791
Additional Information:© 2014 SFoCM. Received: 19 February 2012; Revised: 1 November 2013; Accepted: 16 June 2014; Published online: 23 September 2014. Lerman and Zhang were supported in part by the IMA and by NSF Grants DMS-09-15064 andDMS-09-56072.McCoy and Tropp were supported by Office of Naval Research (ONR) Awards N00014-08-1-0883 and N00014-11-1002, Air Force Office of Scientific Research (AFOSR) Award FA9550-09-1-0643, Defense Advanced Research Projects Agency (DARPA) Award N66001-08-1-2065, and a Sloan Research Fellowship. The authors thank Eran Halperin, Yi Ma, Ben Recht, Amit Singer, and John Wright for helpful conversations. The anonymous referees provided many thoughtful and incisive remarks that helped us improve the manuscript immensely.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0883
Office of Naval Research (ONR)N00014-11-1002
Air Force Office of Scientific Research (AFOSR)FA9550-09-1-0643
Defense Advanced Research Projects Agency (DARPA)N66001-08-1-2065
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Robust linear models; Convex relaxation; Iteratively reweighted least squares
Issue or Number:2
Record Number:CaltechAUTHORS:20150416-134303719
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:56730
Deposited By: Tony Diaz
Deposited On:17 Apr 2015 03:10
Last Modified:03 Oct 2019 08:16

Repository Staff Only: item control page