Robust Computation of Linear Models by Convex Relaxation

By Gilad Lerman, Michael B. McCoy, Joel A. Tropp, Teng Zhang. 2012

167 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “…subspace and its orthogonal complement, respectively, then UU> +BB> is the identity matrix, and we have ‖UU>Yt − Yt‖2F = ‖BB>Yt‖2F = ‖Y >t B‖2F. (33) Note that relation (33) was discussed by Tsakiris & Vidal (2018) in a different context, in comparison to the algorithm of Lerman et al. (2015).”
Adversarially Learned One-Class Classifier for Novelty Detection (2018, methodology): “[22] described a convex optimization problem for detecting the outliers and called it REAPER, which can reliably ﬁt a low-dimensional model to the target class samples.”
Generative Probabilistic Novelty Detection with Adversarial Autoencoders (2018, methodology): “OutRank[55,56] CoP[57] REAPER[58] OutlierPursuit[59] LRR[60] DPCP [61] ℓ 1 thresholding[25] Coil-100 dataset.”
Dual Principal Component Pursuit (2015, methodology): “…DPCP-d (Algorithm 3), RANSAC (Fischler and Bolles, 1981), SE-RPCA (Soltanolkotabi and Candès, 2012), `21-RPCA (Xu et al., 2012), the IRLS version of REAPER (Lerman et al., 2015), as well as Coherence Pursuit (CoP) (Rahmani and Atia, 2017); see §2 for details on these last five existing methods.”
Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery (2017, background): “In later work, Lerman et al. [59] suggested a tighter convex relaxation of the original problem.”