Sparse Representation Classification Beyond ℓ1 Minimization and the Subspace Assumption

Cencheng Shen, Li Chen, Yuexiao Dong, Carey E. PriebeIEEE Trans. Information Theory 2020 · DOI

TL;DR

This paper introduces a faster and more robust version of the Sparse Representation Classifier (SRC) by replacing computationally expensive $\ell_1$ minimization with a screening procedure. The authors prove its classification consistency under various conditions, including latent subspace models and data contamination, demonstrating comparable accuracy to the original SRC but with significant speed improvements.

What Problem Does This Paper Address?

The Sparse Representation Classifier (SRC) has shown great success in tasks like face recognition, leveraging the idea that data from the same class can be represented by a sparse combination of training samples from that class. The original SRC relies on $\ell_1$ minimization to find this sparse representation, which is computationally intensive, especially for high-dimensional data. While effective, the reliance on $\ell_1$ minimization and the strict subspace assumption can be limiting. This paper aims to address these limitations by proposing a faster SRC algorithm that is also theoretically grounded in its robustness to noise and its consistency under more relaxed assumptions.

Methods

The core innovation of this paper is the replacement of the $\ell_1$ minimization step in SRC with a screening procedure. Instead of solving a complex optimization problem, the new algorithm efficiently selects a subset of training samples that are most correlated with the testing observation. This screening step is followed by a least squares regression to find the coefficients and then a classification rule. The authors propose two classification rules: the magnitude rule (based on minimizing regression residuals) and the angle rule (based on maximizing the angle between the test sample and the reconstructed sample from each class). They prove that these rules are equivalent under certain conditions and opt for the angle rule in their new algorithm due to its direct path to theoretical consistency.

The paper also delves into theoretical analysis, proving the classification consistency of their proposed algorithm under a latent subspace mixture model. This model assumes that data from each class lies in a lower-dimensional subspace, but it relaxes the strict requirement that these subspaces are perfectly separated. Crucially, they also investigate robustness against data contamination, showing that their algorithm remains consistent even when a portion of the features are corrupted or missing, provided certain "angle conditions" between the subspaces are met. Finally, they extend their analysis to the stochastic block model, a popular model for network data.

Datasets

The paper evaluates its proposed algorithm on several datasets:

  • Image Data:
    • Extended Yale B database (face recognition)
    • Columbia Object Image Library (Coil20) (object recognition)
  • Network Data:
    • Wikipedia article hyperlinks (directed, unweighted graph)
    • C. elegans somatic nervous system (undirected, unweighted graph)

The authors also use simulated data generated from the Latent Subspace Mixture Model and the Stochastic Block Model to validate their theoretical findings.

Key Insights and Ideas

  • Screening is a Viable Alternative to $\ell_1$ Minimization: The paper demonstrates that a simple screening procedure can effectively identify relevant training samples for SRC, offering a significant computational speedup without sacrificing accuracy. This is a major practical advancement.
  • Angle Rule for Theoretical Soundness: The angle rule, while related to the magnitude rule, provides a more direct theoretical link to classification consistency, especially under challenging conditions like data contamination.
  • Robustness to Contamination is Theoretically Guaranteed: The work provides theoretical guarantees for SRC's performance even when data is corrupted, under specific conditions (the angle condition). This is crucial for real-world applications where data is rarely perfect.
  • Subspace Assumption Can Be Relaxed: The latent subspace mixture model allows for overlapping subspaces between classes, making the theoretical framework more general and applicable to a wider range of real-world scenarios than previous strict subspace assumptions.
  • SRC's Advantage in High Dimensions: The paper reiterates and theoretically supports SRC's effectiveness in high-dimensional settings where traditional classifiers often struggle.

Key Results

  • Significant Speedup: The proposed SRC algorithm with screening is substantially faster than the original $\ell_1$-based SRC. For example, on the Yale Face Images dataset, screening-based SRC takes 72.7 seconds compared to 1101.5 seconds for $\ell_1$-based SRC. Similar speedups are observed across all tested datasets.
  • Comparable Accuracy: Despite the speed advantage, the new algorithm achieves comparable, and in some cases even better, classification accuracy. For instance, in the Coil20 dataset, the screening-based SRC with the angle rule achieves an error rate of 0.01%, matching the best performance.
  • Robustness Demonstrated: Experiments show that the screening-based SRC performs well even with up to 50% pixel contamination in image data, with error rates increasing significantly but still maintaining a competitive performance compared to the original SRC.
  • Theoretical Consistency: The paper provides theoretical proofs for the classification consistency of the proposed algorithm under various models, including latent subspace mixture models and stochastic block models, with and without contamination.

Limitations and Future Work

  • Angle Condition Dependency: The theoretical guarantees for robustness against contamination and consistency under the latent subspace model rely on the "angle condition" between class subspaces. While this condition is shown to hold in many practical scenarios (e.g., random vectors in high dimensions), it's not universally guaranteed.
  • Model Selection: The paper mentions that model selection (e.g., choosing the sparsity level 's') is inherent to variable selection methods and can impact performance, but it's treated as a separate topic for investigation.
  • Future Work: The authors suggest exploring other algorithmic choices for variable selection and classification within the SRC framework, and further investigating the practical implications of the angle condition. They also hint at extending the framework to more complex data structures and scenarios.

Summary updated

BibTeX
@article{shen2020sparse,
  author = {Cencheng Shen and Li Chen and Yuexiao Dong and Carey E. Priebe},
  title = {{Sparse Representation Classification Beyond ℓ1 Minimization and the Subspace Assumption}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  doi = {10.1109/tit.2020.2981309},
}
Figure