PaperlayerView exact revision on arXiv

Source-linked AI summary

An Overview of Robust Subspace Recovery

Gilad Lerman, Tyler Maunu

arXiv:1803.01013v2cs.LGstat.ML

TL;DR

Robust subspace recovery seeks a low-dimensional subspace amid outliers, and this survey reviews its methods and their tradeoffs. It describes RSR as useful for dimension reduction, preprocessing, and visualization, while emphasizing limited empirical quantification and the need for broader evaluation.

  • Problem

    RSR seeks the underlying low-dimensional subspace when a dataset contains inliers and outliers.

    Source: §I · p. 1

  • Method

    The survey discusses RSR methods, computational and memory requirements, empirical comparisons, and future evaluation directions.

    Source: §IV · p. 20, §VII · p. 26

  • Results

    RSR is described as a useful off-the-shelf tool for dimension reduction, preprocessing, and visualization, though quantified success covers only a few datasets.

    Source: 1) Dimensionality Reduction for Data… · p. 21

  • Takeaways & Limitations

    The authors advocate a database of application-specific examples with properly defined success measures and broader testing across tasks.

    Source: §VII · p. 26

    More extensive experimentation with a large database is needed to study RSR's effectiveness as a dimension-reduction tool.

    Source: 1) Dimensionality Reduction for Data… · p. 21

Abstract

from arXiv · show

This paper will serve as an introduction to the body of work on robust subspace recovery. Robust subspace recovery involves finding an underlying low-dimensional subspace in a dataset that is possibly corrupted with outliers. While this problem is easy to state, it has been difficult to develop optimal algorithms due to its underlying nonconvexity. This work emphasizes advantages and disadvantages of proposed approaches and unsolved problems in the area.

I. INTRODUCTION: WHAT IS ROBUST SUBSPACE RECOVERY?

Robust subspace recovery (RSR) seeks the underlying low-dimensional subspace in data containing inliers and outliers, a challenging nonconvex problem. The survey distinguishes RSR from sparse-corruption RPCA and reviews formulations, algorithms, guarantees, and open directions.

I. INTRODUCTION: WHAT IS ROBUST SUBSPACE RECOVERY?

  • RSR targets the underlying subspace of inliers and outliers, unlike sparse-corruption RPCA, which seeks the full low-rank matrix in an elementwise-sparse decomposition.Outlier-robust methods address the former setting; RPCA commonly refers to the latter.Source: §I · p. 1

A. Roadmap

  • The survey reviews RSR formulations and algorithms, recovery guarantees and data models, computational and memory costs, empirical comparisons, applications, and future directions.It also proposes a substantial database for testing RSR methods.Source: A. Roadmap · p. 2

B. Notation

  • Notation distinguishes high-probability from overwhelming-probability claims and allows nonconvex minimizers or maximizers to be nonunique.The paper defines these probability scales in terms of N and writes estimators as belonging to argmin or argmax sets.Source: B. Notation · p. 2

II. BASIC FORMULATIONS FOR ROBUST SUBSPACE RECOVERY

  • The survey assumes a linear subspace for its main discussion, while affine subspaces are deferred to future-work discussion.The target is L in G(D, d), equivalently represented by a matrix whose columns span L.Source: §II · p. 2

A. Review of Subspace Modeling by PCA

  • PCA has a direct solution: its d-subspace is spanned by the top d eigenvectors of the scaled sample covariance, or the top d left singular vectors of X.The solution is unique when the dth and (d + 1)st eigenvalues differ.Source: A. Review of Subspace Modeling by PCA · p. 2

B. Difficulties of Developing Outlier-Robust PCA

  • Robust estimation is harder than PCA because defining a robust estimator and calculating it are both challenging; even an ℓ1 relaxation of the ℓ0 formulation remains NP-hard.For noisy inliers, choosing the noise parameter is also unclear, and the formulations may have nonunique solutions.Source: B. Difficulties of Developing… · p. 3
  • The noisy ℓ1 formulation may give poor estimates when noise is nonuniform around the subspace or when overestimated noise tolerance merges nearby outlier subspaces.The survey also notes that no general easy approximation is available for the ℓ0 or ℓ1 formulations.Source: B. Difficulties of Developing… · p. 3

C. Projection Pursuit

Projection pursuit seeks directions maximizing a robust scale, often finding multiple components sequentially. Least absolute deviations offers a rotation-invariant subspace objective, but its optimization is difficult despite useful IRLS approaches.

C. Projection Pursuit

  • Projection pursuit replaces variance with a robust scale function and seeks a direction maximizing that scale; its maximization is generally nonconvex and exhaustive search is non-polynomial time.Past methods use iterative reweighting, bit-flipping, or convex relaxation to find local or approximate global maxima.Source: C. Projection Pursuit · p. 3

D. Least Absolute Deviations

  • For d = 1, projection pursuit with the L1 scale coincides with least absolute deviations, while the broader formulations need not have the same solutions.The ℓ0-to-ℓ1 relaxation motivates least absolute deviations, and related hyperplane fitting can be expressed as the same objective for d = D −1.Source: C. Projection Pursuit · p. 3, D. Least Absolute Deviations · p. 4

C. Projection Pursuit

  • Multiple projection-pursuit components can be found sequentially by maximizing the same objective subject to orthogonality with previously found vectors.A joint-energy variant seeks an approximate global maximizer, as in MDR [74].Source: C. Projection Pursuit · p. 3

D. Least Absolute Deviations

  • Least absolute deviations minimizes summed orthogonal distances to a subspace and is rotationally invariant, but approximately minimizing it is NP-hard.IRLS approaches recast the problem as weighted PCA, while one approximate polynomial-time solution for fixed d has a large absolute factor [76].Source: D. Least Absolute Deviations · pp. 3–4

1) Convex Relaxations:

Convex relaxations approximate least absolute deviations using outlier-pursuit and subspace-estimation formulations. Their parameters and outputs differ, while IRLS procedures provide efficient optimization approaches.

1) Convex Relaxations:

  • Outlier pursuit relaxes least absolute deviations with nuclear- and column-norm penalties, making the program convex and allowing proximal-gradient optimization.Replacing the nuclear norm with rank shows that the column-norm term measures summed distances from data points to the subspace.Source: 1) Convex Relaxations · p. 4
  • The authors report that λ = 3/(7√Nout) did not perform well in their tested settings and instead choose λ = 0.8 D/N.The usual parameter requires guessing an upper bound on the unknown number of outliers.Source: 1) Convex Relaxations · p. 4
  • GMS estimates the subspace from the bottom eigenvectors of a relaxed inverse-covariance estimator, while REAPER estimates an orthoprojector and uses its top eigenvectors.Both methods use IRLS to solve their convex relaxations.Source: 1) Convex Relaxations · pp. 4–5

2) Nonconvex Optimization:

Direct nonconvex optimization can be faster in special settings but is difficult to justify theoretically. The survey distinguishes L1-PCA formulations, noting that their robustness, invariance, and computational properties vary.

2) Nonconvex Optimization:

  • Direct nonconvex optimization may yield faster algorithms in special settings, but theoretical justification is difficult despite practical performance.Recent theory establishes strengths only in certain regimes.Source: 2) Nonconvex Optimization · p. 5
  • FMS applies IRLS directly to least absolute deviations, while GGD uses geodesic gradient descent; FMS seems better in practice, but GGD has stronger existing guarantees [73].R1PCA uses a power-method variant that may produce poor solutions because its technique is tied to convex methods.Source: 2) Nonconvex Optimization · p. 5
  • TORP alternates PCA fitting with filtering distant or highly incoherent points, but requires an input outlier percentage that may be overestimated when outliers are sufficiently few.DPCP sequentially fits nested hyperplanes using linear programs, continuing until a d-subspace remains [103].Source: 2) Nonconvex Optimization · p. 5

E. L1-PCA

  • L1-PCA minimization corresponds to an MLE under Laplacian noise, but its elementwise-corruption robustness may be less suited to outliers; it is NP-hard for d < D −1 [35].A polynomial-time algorithm is available for d = D−1, while approximate minimization is studied in.Source: E. L1-PCA · p. 6
  • L1-PCA maximization is tied to projection pursuit and RSR, unlike minimization's RPCA connection, but the formulation is not rotation invariant and is NP-hard for large N and D [74].IRLS formulations face least-squares subproblems that are not easy to solve globally.Source: E. L1-PCA · p. 6

F. Robust Covariances

Robust covariance estimators offer a route to principal subspaces, including in affine settings; the survey also reviews spherical covariance and trimmed-energy approaches. Their computational and statistical conditions vary.

F. Robust Covariances

  • Robust covariance estimates can locate principal subspaces through their top eigenvectors, with direct synthesis for subspace recovery in.Source: F. Robust Covariances · p. 6
  • The estimators in (28) and (29) are geodesically convex and computable by IRLS, but are undefined when D > N and may be ill-conditioned when D ≤ N.Regularization is commonly used for the ill-conditioned case.Source: F. Robust Covariances · p. 7
  • Spherical PCA takes the principal subspace of the spherical sample covariance, equivalent to PCA on normalized data; pairwise differences also support covariance estimation when the mean is unknown.Source: F. Robust Covariances · p. 7
  • For affine recovery, symmetrized robust covariance estimates the linear component from pairwise differences, avoiding prior offset centering and its potentially amplified error.Source: F. Robust Covariances · p. 7

G. Other Energy Minimizers

H. Filtering Outliers

The survey reviews filtering and exhaustive-search strategies for RSR, alongside related problems and the structure of theoretical recovery guarantees. The methods use varied criteria and assumptions.

H. Filtering Outliers

  • Affinity-based filtering removes low-degree points, while Self-Representation Outlier Detection [116] iterates an elastic-net weight matrix to seek support on inliers.Source: H. Filtering Outliers · p. 7
  • Coherence Pursuit [90] ranks points by degrees in a symmetric weight matrix and is the fastest method in its framework, but struggles with noise and requires an unknown noise-level estimate in its iterative variant.Source: H. Filtering Outliers · p. 8
  • HR-PCA trims points with high variance in the current direction, but requires the outlier percentage and is not intuitively justified for subtler outliers.A deterministic version, DHRPCA, was later developed [31].Source: H. Filtering Outliers · p. 8
  • Adaptive compressive sampling [58] filters subsampled data before fitting a subspace from unfiltered full-dimensional points; TORP [17] can also be viewed as filtering.Source: H. Filtering Outliers · p. 8

I. Exhaustive Subspace Search Methods

  • RANSAC samples points and selects a subspace by consensus, while RandomizedFind and DeRandomizedFind search for dependent subsets, with a noisy variant using a determinant threshold.The section also notes scan-statistic search for robust manifold recovery.Source: §I · p. 8

J. Parallel Works

  • Related work includes robust orthogonal regression using least absolute deviations and RPCA methods across optimization and online settings; the survey describes these developments as complementary.Source: J. Parallel Works · p. 8

III. THEORETICAL RECOVERY GUARANTEES

  • The theoretical section compares exact recovery for noiseless data with near recovery for noisy data, where approximation error is typically bounded by a function of noise level.It organizes guarantees by algorithm category and compares them for a specific statistical model.Source: §III · p. 9

A. Assumption on and Models of Data

The survey frames theoretical RSR around inliers near a fixed subspace and outliers in the ambient space, usually with known dimension. It develops inlier permeance and restricted outlier alignment as principles for well-defined models.

A. Assumption on and Models of Data

1) Restrictions on the Inliers and a First Principle:

  • Inliers concentrated at the origin or on a lower-dimensional part of the target can leave the underlying subspace ill-defined, motivating the principle of permeance.Inliers must fill the target subspace, though nonuniform sampling and very low-level concentration may be tolerated.Source: 1) Restrictions on the Inliers and a… · p. 9

2) Restrictions on the Outliers and a Second Principle:

  • The meaning of “most significant” is problematic with noisy data: nearby outlier subspaces can jointly appear more populated, and the proposed combined-count notion is limited to a specific model.Source: 2) Restrictions on the Outliers and a… · p. 11
  • Outlier alignment must be restricted so outliers do not form a competing significant subspace; the needed restriction depends on the inlier distribution and outlier regime.Some methods also require controls on relative magnitudes, since large outliers can unduly influence a criterion.Source: 2) Restrictions on the Outliers and a… · pp. 9, 11, 12
  • Scale-invariant methods normalize points to remove dependence on magnitude, but normalization can emphasize a differently aligned small-outlier subspace; alignment restrictions still matter.The survey notes that this normalization is unclear with missing data or affine settings.Source: 2) Restrictions on the Outliers and a… · p. 12

3) Stability: the Combination of Permeance and Alignment:

The section relates RSR recovery guarantees to stability conditions and data models, then surveys algorithmic analyses and their limitations.

3) Stability: the Combination of Permeance and Alignment:

  • A stability constraint combines inlier permeance with restricted outlier alignment, but near its lower bound these quantities trade off and are assessed separately.Some such constraints imply an upper bound on the outlier percentage, expressible as a lower bound on the inlier-to-outlier SNR.Source: 3) Stability: the Combination of… · p. 12

4) Specific Models of RSR:

  • For arbitrary outliers, bounds can require relatively high SNR; encouraging inlier permeance may permit lower SNR, but further model and guarantee study is needed.Some results in this model require scale-invariant algorithms because outlier magnitudes are unrestricted.Source: 4) Specific Models of RSR · pp. 12–13
  • In the general-position model, the optimal SNR is d/(D−d), and meeting that bound reduces noiseless RSR to finding a linearly dependent D-subset [41].This model’s exact-recovery assumptions limit its relevance to some real datasets and its extension to noisy near recovery.Source: 4) Specific Models of RSR · p. 13
  • Theoretical RSR results chiefly address noiseless exact recovery, with only a few works focused on truly noisy settings.The haystack model compares guarantees under Gaussian inliers on the subspace and isotropic Gaussian outliers; its generalized form remains specialized.Source: 4) Specific Models of RSR · p. 13

B. Sequential Methods and Projection Pursuit

  • Sequential recovery can compound noise to Ω(dϵ), or Ω((D−d)ϵ) when fitting orthogonal-complement hyperplanes.Each successive component may move farther from the underlying subspace after projection.Source: B. Sequential Methods and Projection… · p. 13
  • Projection pursuit lacks substantial theoretical guarantees, and sequential methods need not recover a stationary point of the joint subspace energy [74, 76].Even without noise, least-absolute-deviations minimization can yield a first direction outside the underlying subspace in general inlier-outlier settings.Source: B. Sequential Methods and Projection… · p. 13

C. Least Absolute Deviations

  • Most theoretical guarantees concern least-absolute-deviation methods, while the reviewed outlier-pursuit theory has weak arbitrary-outlier SNR and relatively large near-recovery noise bounds.The cost’s nuclear-norm rank approximation treats an outlier’s orthogonal component similarly in both cost terms; outlier pursuit is scale-invariant for sufficiently large SNR.Source: C. Least Absolute Deviations · p. 14, 1) Guarantees for Outlier Pursuit · p. 14

1) Guarantees for Outlier Pursuit:

  • Under Xu et al.’s assumptions, outlier pursuit recovers L and C exactly.For noisy data, the supplied theorem states a near-recovery bound when SNR ≥1024µd/9 and ∥N∥F ≤ ϵ.Source: 1) Guarantees for Outlier Pursuit · p. 14

2) Guarantees for GMS and REAPER:

The surveyed guarantees range from stability-based exact recovery for GMS and REAPER to method-specific guarantees for nonconvex least-absolute-deviation approaches, often under restrictive data conditions. In general, convergence of these nonconvex methods to a stationary point does not establish that the result recovers a useful subspace.

2) Guarantees for GMS and REAPER:

  • GMS recovery has deterministic stability conditions, but its strong outlier-alignment restriction requires at least 1.5D outliers filling ambient space for good accuracy.The survey also notes that the authors establish these conditions with overwhelming probability under certain sub-Gaussian mixture and haystack models, and extend them to near recovery for near-subspace inliers.Source: 2) Guarantees for GMS and REAPER · p. 14
  • Positive stability guarantees REAPER exact recovery in the noiseless case; in general settings, stability must exceed the total inlier residual for the solution to approximate the underlying subspace.The stability statistic compares inlier permeance with outlier alignment; the approximation bound is meaningful only when stability exceeds the residual.Source: 2) Guarantees for GMS and REAPER · pp. 14–15

3) Guarantees for Nonconvex Formulations of Least Absolute Deviations:

  • Least-absolute-deviations energy minimization can recover exactly under a specified probabilistic mixture model, but that analysis does not guarantee an algorithm for minimizing it.The model is restrictive and the estimates require large sample sizes.Source: 3) Guarantees for Nonconvex… · p. 15
  • FMS converges to a stationary point and monotonically decreases the least-absolute-deviations energy; near recovery is shown only for two special inlier–outlier settings.Those settings include spherically symmetric outliers with inliers spherically symmetric within the subspace, or outliers spherically symmetric or on a less significant one-dimensional subspace with inliers on a significant one-dimensional subspace; the estimates require large samples.Source: 3) Guarantees for Nonconvex… · p. 15
  • GGD initialized within a stability-defined neighborhood exactly recovers the subspace; under a strong-gradient condition, it can converge linearly.The survey reports recovery guarantees almost on par with the strongest convex methods on the haystack model, but with sample estimates N = O(D^2 log(D)) versus O(D) for REAPER and GMS.Source: 3) Guarantees for Nonconvex… · pp. 15–16
  • TORP linearly converges to exact recovery under its noiseless assumptions, while its noisy-data guarantee bounds subspace approximation error and its arbitrary-corruption theory requires the outlier fraction to be known.The survey notes that its bounds for generative models such as the haystack model are weaker than those for REAPER and GGD.Source: 3) Guarantees for Nonconvex… · p. 16
  • DPCP proves recovery under deterministic conditions that are difficult to interpret, while the surveyed R1PCA formulation has no global-optimality or subspace-recovery guarantees.For general datasets, these nonconvex methods are proven to converge at best to a stationary point, whose usefulness is not known in general.Source: 3) Guarantees for Nonconvex… · pp. 15–16

D. L1-PCA

The survey reports no known recovery or robustness guarantees for L1-PCA, while noting that guarantees for a similar RPCA problem are reviewed elsewhere.

D. L1-PCA

  • The survey reports no known recovery or robustness guarantees for L1-PCA, and directs readers to a review of guarantees for the similar RPCA problem.Source: D. L1-PCA · p. 16

E. Robust Covariance Estimation

The survey distinguishes covariance breakdown-point analysis from subspace recovery, then reviews TME and several outlier-removal methods with guarantees tied to specific models and conditions. It highlights limits in how broadly those results apply and, for some methods, in what they establish about subspace approximation.

E. Robust Covariance Estimation

  • Covariance breakdown points do not transfer directly to subspace recovery because the Grassmannian is compact; lowest-SNR recovery criteria are weaker notions.Source: E. Robust Covariance Estimation · p. 16
  • TME exactly recovers the subspace under noiseless general-position assumptions when SNR > d/(D − d).The survey also notes that TME is scale-invariant, whereas spherical PCA cannot exactly recover subspaces.Source: E. Robust Covariance Estimation · p. 16

F. Other Energy Minimization and Filtering Outliers

  • The outlier-removal energy of Xu and Yuille has no associated guarantees for subspace recovery.Source: F. Other Energy Minimization and… · p. 16
  • HR-PCA and DHRPCA are assessed using expressed variance, a 0-to-1 measure of underlying variance captured; the cited Gaussian-model lower bound is 0.09.An expressed variance of 1 amounts to exact recovery.Source: F. Other Energy Minimization and… · pp. 16–17
  • Outlier-removal guarantees for robust manifold clustering and noiseless single-subspace recovery require specified sampling models, and some require a uniformly random inlier subspace.The survey also notes that You et al. prove exact outlier recovery under conditions not verified for a generative model.Source: F. Other Energy Minimization and… · p. 17
  • CP recovery guarantees cover special data models, but noisy recovery of a core inlier set may not approximate the underlying subspace well.The survey says the theory lacks bounds on subspace approximation error for the identification algorithm.Source: F. Other Energy Minimization and… · p. 17

G. Exhaustive Subspace Search

The survey compares recovery guarantees under exhaustive search and the haystack model, then weighs algorithm runtime, convergence, and memory costs. It highlights assumptions and settings where guarantees weaken or remain unavailable.

G. Exhaustive Subspace Search

  • Above SNR d/(D − d), noiseless general-position RandomizedFind and DeRandomizedFind recover L* in expected O(1) iterations and polynomial time, respectively.Below that threshold, the problem is small-set-expansion hard, which is conjectured to be NP-hard; neither method has existing noisy-setting theory.Source: G. Exhaustive Subspace Search · p. 17
  • RANSAC succeeds when the noiseless problem is well-defined, but low SNR raises computational time; near recovery requires correctly set parameters and further outlier-alignment assumptions.Source: G. Exhaustive Subspace Search · p. 17

H. Recovery with the Haystack Model

  • For N = O(D), the haystack model’s optimal SNR is on the order of d/[D(D − d]; GGD achieves that bound but requires N = O(D²).The table compares lower bounds across orders of N and summarizes guarantees, including results under possibly different models.Source: H. Recovery with the Haystack Model · p. 18, Table I · p. 18
  • As N → ∞, GGD and CP tolerate any fixed outlier fraction; FMS also tolerates one but only nearly recovers to regularization-dependent precision.CP theory requires d < D, while REAPER requires d < (D − 1)/2; other methods can tolerate any d < D.Source: H. Recovery with the Haystack Model · p. 18

IV. COMPUTATIONAL COMPLEXITY AND MEMORY REQUIREMENTS

  • Although complexity comparisons assume constant T for many iterative algorithms, only GMS and GGD have conditional r-linear guarantees, TORP has a linear guarantee, and several methods converge sublinearly.The survey notes that slow convergence is expected in some cases because the problem is NP-hard.Source: §IV · p. 18
  • FMS, GGD, and TORP run in T · O(NDd), while GMS, REAPER, and TME incur O(ND²) covariance costs; ACOS subsampling can weaken guarantees and refitting may erase speedups.ConstApprox can run in O(ND) on dense input but has no guarantee of recovering a subspace.Source: §IV · pp. 19–20
  • Online MKF and RMD have a hidden factor of N in iteration cost, and their unknown sample complexity may require enough passes to make them slower in practice.Source: §IV · p. 20
  • Memory costs reflect each method’s storage strategy: CP and SRO store an N × N weight matrix, while online MKF can stream data and retain only an estimator per iteration.O(D²) storage is typical for covariance-type estimators, lifting relaxations, or methods storing a set of D points; O(ND) is typical when storing the full data matrix.Source: §IV · p. 20

V. NUMERICAL EXPERIMENTS AND APPLICATIONS

The survey reviews RSR experiments and argues that performance should be measured by ground-truth subspace distance on synthetic data and application-specific outcomes on real data. Real-data evidence remains limited, motivating broader evaluation.

V. NUMERICAL EXPERIMENTS AND APPLICATIONS

  • Synthetic RSR accuracy should be measured by distance from the ground-truth subspace, while real-data success should be judged by the application rather than an algorithm-specific energy.For enhanced clustering, the cited comparison uses clustering accuracy.Source: §V · p. 20

A. Experiments with RSR on Real Datasets

  • Real-data experimentation is limited because RSR is a general-purpose tool, and the survey calls for more realistic datasets and application-tied measures of success.A proposed direction is a database for testing RSR as a dimension-reduction preprocessor.Source: A. Experiments with RSR on Real Datasets · p. 20

1) Dimensionality Reduction for Data Preprocessing:

  • On Fisher’s iris data, McCoy and Tropp [74] report visually that low-leverage decomposition captures more variation of the inlier flower type than PCA, without quantifying the difference.The experiment treats observations from other flower types as corruptions.Source: 1) Dimensionality Reduction for Data… · p. 21
  • Across the reviewed preprocessing examples, RSR is described as useful for dimension reduction, preprocessing, and visualization, but success has been quantified on only a few datasets.The survey calls for more extensive evaluation on a larger database.Source: 1) Dimensionality Reduction for Data… · p. 21

2) Image Data:

  • The handwritten-digit subspace experiment was visual-only, with no quantitative performance measures; for video surveillance, the authors argue RSR is unsuitable and sparse-corruption RPCA models the task better.Source: 2) Image Data · p. 21

B. Experiments with RSR on Synthetic and Stylized Datasets

The survey reviews synthetic and stylized RSR comparisons, including a haystack simulation and a proposed blurryface model. Results vary with the data model, and the authors emphasize both model limitations and conditional algorithm performance.

1) Review of Experiments on Synthetic Data:

  • In the reviewed synthetic literature, comprehensive comparisons are scarce, and the survey identifies Lerman and Maunu as providing the most extensive Gaussian-model comparison known to the authors.The face-subspace application is stylized, with other natural images serving as outliers.Source: 1) Review of Experiments on Synthetic… · p. 21
  • In the broader haystack comparisons, FMS and TME were most robust to high outlier percentages in most cases, while TME had higher runtime than FMS.The survey notes that haystack recovery can be easy for some algorithms and that simple statistics can distinguish inliers from outliers when data are not sphere-normalized.Source: 1) Review of Experiments on Synthetic… · p. 21, 2) Haystack Model Simulation · p. 21

2) Haystack Model Simulation:

  • On haystack data, FMS, SFMS, TME, SGGD, and SRO are most accurate, with FMS the fastest among them; TORP performs well only when the outlier fraction is known.CP is fast on these tests because it is non-iterative, but the authors note it may not scale as well to large datasets.Source: 2) Haystack Model Simulation · p. 22

3) The Blurryface Model and Simulations:

  • The proposed blurryface model tests recovery of a 9-dimensional face subspace with outliers, using synthetic data intended to mimic some real-data statistics.The inlier faces differ from natural face images, while the outliers lie in a cone and are asymmetric, making recovery harder than under the haystack model.Source: 3) The Blurryface Model and Simulations · p. 22
  • For spherical blurryface inliers, TORP and TME appear most accurate and FMS/SFMS are fastest among accurate methods; for elliptical inliers, TME is most accurate, while FMS/SFMS are fastest and TME is much slower.TORP requires the correct outlier percentage for its spherical-model performance and fails on the elliptical model even when that percentage is known.Source: 3) The Blurryface Model and Simulations · p. 23

VI. INFLUENCE OF RSR ON OTHER METHODS

The survey describes ways RSR connects to clustering, computer vision, and other recovery problems, while identifying substantial open questions. These include theoretical guarantees, sample requirements, dimension estimation, noise robustness, and broader experimentation.

VI. INFLUENCE OF RSR ON OTHER METHODS

  • RSR-based outlier filtering can support robust subspace clustering, and sequential RSR strategies have been used, but general sequential approaches face geometric obstacles absent restrictive assumptions.K-subspace approaches lack algorithmic guarantees in the cited discussion and require knowledge of the intrinsic subspace dimensions.Source: §VI · pp. 23–24
  • RSR methods and IRLS ideas have influenced robust camera-location and synchronization methods, although pairwise-direction outliers lack a simple subspace geometric model.The survey also identifies robust fundamental or essential matrix estimation as an RSR formulation, with specially tailored variants potentially outperforming existing methods [91].Source: §VI · pp. 24–25

VII. FUTURE WORK

  • Online RSR algorithms have unsatisfactory guarantees and performance, and their required sample counts for convergence are unknown.The survey also notes distributed RSR optimization under certain conditions when communication is limited by network structure [45].Source: §VII · p. 25
  • RSR dimension estimation remains undeveloped, although the fastest algorithms require the subspace dimension in advance and do not produce nested subspaces for easy cross-dimension comparison.The survey also identifies affine-subspace estimation as understudied, with no established practical advantage over centering by the geometric median.Source: §VII · p. 25
  • The survey calls for broader experiments using application-specific success measures and notes that random projections become harder for RSR at low SNR.It also identifies optimal rates and other noise regimes as open problems, and says current adversarial-outlier results are weak.Source: §VII · pp. 25–26

APPENDIX

The appendix relates robust covariance estimation to heavy-tailed elliptical likelihoods and describes iterative estimators. The Student’s t case requires an additional constraint for uniqueness, unlike the stated Maronna conditions.

A. Intuition for the Robust Covariance Matrices

  • For centered elliptical data, the robust energies are scaled negative log-likelihoods, so Maronna and Tyler M-estimators can be viewed as likelihood estimators robust to heavy tails.In the Gaussian case, the stated weighted covariance solution reduces to the sample covariance matrix.Source: A. Intuition for the Robust Covariance… · p. 30
  • With heavier-tailed models, the covariance update weights each data term by a function of its Mahalanobis distance, tending to de-emphasize outliers.For the stated power-tail example, the weight is (x_i^T Σ^-1 x_i)^(p-1).Source: A. Intuition for the Robust Covariance… · p. 30
  • The Student’s t energy does not have a unique positive-definite solution without an added constraint such as tr(Σ) = 1, whereas the stated Maronna conditions guarantee a unique minimizer.The Student’s t weight is (D + ν)/(t + ν).Source: A. Intuition for the Robust Covariance… · p. 30
  • For ρ functions satisfying the required conditions, the Maronna M-estimator’s stated iteration allows any positive-definite initialization; TME uses w(t)=D/t and normalizes Σk+1 so tr(Σk+1)=1.Numerical properties of the TME solution are discussed in and.Source: A. Intuition for the Robust Covariance… · pp. 30–31
Loading 1803.01013v2…