Fisher Discriminative Least Squares Regression for Image Classification

Zhe Chen, Xiao-Jun Wu, Josef Kittler

TL;DR

The paper introduces Fisher Discriminative Least Squares Regression (FDLSR), a novel framework for image classification that combines the label-relaxing power of $\epsilon$-draggings with the class-tightening power of the Fisher criterion. By simultaneously widening inter-class margins and enforcing intra-class compactness, FDLSR achieves state-of-the-art classification accuracy while training up to 100 times faster than traditional sparse representation methods.

What Problem Does This Paper Address?

In multi-class image classification, Least Squares Regression (LSR) is a popular choice due to its simplicity and computational efficiency. However, traditional LSR forces training samples into a strict binary label space (e.g., 0s and 1s), assuming the distance between any two different classes is a constant. This rigid assumption doesn't reflect real-world data distributions well.

To fix this, prior work introduced Discriminative LSR (DLSR), which uses a technique called $\epsilon$-draggings to relax these strict labels, allowing inter-class margins to expand. But DLSR introduced a new headache: during optimization, the relaxed labels within the same class can drift apart randomly, becoming uncorrelated. This lack of intra-class compactness leads to overfitting and limits classification performance, especially on large-scale or highly variable datasets.

Methods

The authors propose Fisher regularized DLSR (FDLSR) to get the best of both worlds. They integrate the classic Fisher discrimination criterion directly into the DLSR framework.

The core formulation relies on two complementary forces:

  1. $\epsilon$-Draggings: Pushes regression labels of different classes in opposite directions to maximize inter-class separability.
  2. Fisher Criterion: Pulls regression labels of the same class closer together to maximize intra-class compactness.

To make this complex joint optimization problem mathematically tractable, the authors introduce a transition variable ($T$) that decouples the objective function. This allows them to solve the problem using an efficient, three-step iterative optimization algorithm where every single variable ($T$, the projection matrix $Q$, and the relaxation matrix $S$) has a closed-form solution. This eliminates the need for time-consuming gradient descent or $l_0/l_1$-norm sparse optimizations.

Datasets

The authors evaluated FDLSR across eight diverse, publicly available benchmarks:

  • Face Recognition: AR, CMU PIE, FERET, and LFW (Labeled Faces in the Wild).
  • Object Recognition: COIL-100.
  • Large-Scale / Fine-Grained Datasets (using pre-trained VGG features): Stanford-40 Actions, Caltech-UCSD Birds (CUB200-2011), and Oxford 102 Flowers.

Key Insights and Ideas

  • Opposites Attract (and Distract): The true innovation is realizing that $\epsilon$-draggings and the Fisher criterion are perfectly complementary. One expands the global boundaries between classes, while the other prevents internal class structure from dissolving during that expansion.
  • Bypassing the Sparse Coding Bottleneck: Many state-of-the-art dictionary learning methods (like FDDL or SRC) rely on $l_0$ or $l_1$ norms to enforce sparsity, which is computationally brutal. FDLSR proves that you can achieve comparable or superior discriminative power using an $l_2$-norm formulation with closed-form solutions, slashing training times drastically.
  • Iterative Margin Widening: Unlike standard DLSR where class margins typically stop expanding after the first iteration, FDLSR’s inclusion of the Fisher term forces margins to continuously widen step-by-step throughout the optimization process.

Key Results

  • Superior Accuracy: FDLSR consistently outperformed standard DLSR, ReLSR, and robust dictionary learning methods across almost all datasets. It proved particularly powerful in Small-Sample-Size Problems (SSSP), where only 2 or 3 training samples per class were available.
  • Massive Speedups: FDLSR proved to be over 100 times faster in training than sparse-representation-based classifiers like SRC and FDDL.
  • Rapid Convergence: As shown in the paper's convergence analysis, the objective function monotonically decreases and stabilizes within roughly 30 iterations across all eight datasets, making its computational overhead highly predictable.
Objective function value and recognition rate vs. iterations

Limitations and Future Work

The primary limitation of FDLSR is the Single Sample Per Person (SSPP) problem. If a class contains only one training sample, the concept of "intra-class similarity" becomes meaningless. Under these conditions, the Fisher criterion fails to provide any regularizing benefit, causing FDLSR's performance to drop sharply down to the level of standard DLSR.

Future work could explore adapting the framework to handle single-sample scenarios, perhaps by incorporating self-supervised data augmentation or leveraging structural priors from adjacent domains.

Summary updated

Abstract

Discriminative least squares regression (DLSR) has been shown to achieve promising performance in multi-class image classification tasks. Its key idea is to force the regression labels of different classes to move in opposite directions by means of the proposed the joint use of the $ε$-draggings technique, yielding discriminative regression model exhibiting wider margins, and the Fisher criterion. The $ε$-draggings technique ignores an important problem: its non-negative relaxation matrix is dynamically updated in optimization, which means the dragging values can also cause the labels from the same class to be uncorrelated. In order to learn a more powerful discriminative projection, as well as regression labels, we propose a Fisher regularized DLSR (FDLSR) framework by constraining the relaxed labels using the Fisher criterion. On one hand, the Fisher criterion improves the intra-class compactness of the relaxed labels during relaxation learning. On the other hand, it is expected further to enhance the inter-class separability of $ε$-draggings technique. FDLSR for the first time ever attempts to integrate the Fisher discriminant criterion and $ε$-draggings technique into one unified model because they are absolutely complementary in learning discriminative projection. Extensive experiments on various datasets demonstrate that the proposed FDLSR method achieves performance that is superior to other state-of-the-art classification methods. The Matlab codes of this paper are available at https://github.com/chenzhe207/FDLSR.
BibTeX
@misc{chen2019fisher,
  author = {Zhe Chen and Xiao-Jun Wu and Josef Kittler},
  title = {{Fisher Discriminative Least Squares Regression for Image Classification}},
  year = {2019},
  eprint = {1903.07833},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.07833},
}
Figure