Introduction
In pattern recognition, representation-based classifiers like Sparse Representation-based Classification (SRC) and Collaborative Representation-based Classification (CRC) have set high benchmarks for accuracy. These methods typically represent a query sample as a linear combination of all available training samples. However, they suffer from significant scalability issues. As the training set size ($n$) grows, the computational cost of solving optimization problems (like $l_1$-norm minimization) for every query sample becomes prohibitive. Furthermore, these methods require keeping all training samples in memory during inference.
This paper introduces the Self-Representation Induced Classifier (SRIC) and its discriminative variant (DSRIC). These methods shift the focus from a "sample-oriented" perspective to a "feature-oriented" one. By learning how the features of a specific class represent themselves, the authors develop a classifier that is orders of magnitude faster and more memory-efficient than current state-of-the-art methods while maintaining competitive accuracy.
Methodology
Self-Representation Induced Classifier (SRIC)
The core innovation is the self-representation property. Instead of reconstructing a query image from other images, SRIC asks how each feature (e.g., a pixel) in a class relates to other features within that same class. For each class $k$, the algorithm learns a self-representation matrix $B_k$ by minimizing the reconstruction error: $$\|X_k - B_k X_k\|_F^2 + \lambda \|B_k\|_F^2$$ where $X_k$ is the training data for class $k$. Once learned, a new sample $z$ is classified by projecting it onto each $B_k$ and identifying the class with the smallest residual error.
Discriminative SRIC (DSRIC)
While the basic SRIC is generative, DSRIC adds a discriminative term to the objective function. It forces the matrix $B_k$ to represent its own class features accurately while simultaneously pushing the reconstruction of other classes toward zero. This significantly enhances the model's ability to distinguish between similar classes by widening the gap in residuals.
Theoretical Foundations
The authors prove that basic SRIC is mathematically equivalent to an $l_2$-norm regularized Nearest Subspace Classifier (NSC) and is closely related to Principal Component Analysis (PCA) with eigenvalue shrinkage. Unlike SRC, which requires iterative optimization, DSRIC offers a closed-form solution, making testing a simple matter of matrix-vector multiplication.
Experimental Results
The authors evaluated DSRIC on diverse benchmarks, including UCI datasets, handwritten digits (USPS, MNIST), and face recognition (LFW, AR face database).
Performance and Efficiency
- Speed: On the MNIST dataset, DSRIC was 18,000 times faster than the Nearest Neighbor Classifier (NNC) and 51 times faster than SRC. On UCI datasets, it achieved a speedup of approximately 547x over SRC.
- Memory: DSRIC only needs to store $K$ matrices of size $d \times d$ (where $d$ is the feature dimension), rather than the entire training set of $n$ samples.
- Accuracy: DSRIC achieved 60.8% accuracy on the LFW face database, outperforming both SRC (60.4%) and CRC (58.8%). On UCI datasets, it averaged 85.4% accuracy, roughly 2% higher than its competitors.
Discussion and Conclusion
SRIC and DSRIC represent a paradigm shift in representation-based classification. By decoupling the testing complexity from the number of training samples, these methods are uniquely suited for "Big Data" scenarios.
Key Insights: * Independence from Sample Size: Testing complexity depends only on the feature dimension $d$, making it highly scalable. * Exploiting Correlation: The method effectively captures the high correlation between features in visual data.
Limitations: While highly efficient, the training phase still requires the full training set to compute $B_k$ matrices. Additionally, the current model is linear; future work may explore non-linear "kernelized" versions to handle more complex data manifolds. Despite these areas for growth, DSRIC stands as a powerful, efficient alternative for high-speed pattern recognition.
Summary updated