Abstract
Traditional dictionary learning methods are based on quadratic convex loss function and thus are sensitive to outliers. In this paper, we propose a generic framework for robust dictionary learning based on concave losses. We provide results on composition of concave functions, notably regarding super-gradient computations, that are key for developing generic dictionary learning algorithms applicable to smooth and non-smooth losses. In order to improve identification of outliers, we introduce an initialization heuristic based on undercomplete dictionary learning. Experimental results using synthetic and real data demonstrate that our method is able to better detect outliers, is capable of generating better dictionaries, outperforming state-of-the-art methods such as K-SVD and LC-KSVD.
The Problem: Sensitivity to Outliers
Dictionary Learning (DL) is a fundamental technique in signal processing and computer vision used to find a set of representative "atoms" (a dictionary) that can sparsely represent a dataset. The traditional mathematical formulation uses a squared Frobenius norm (a quadratic loss) to measure how well the dictionary fits the data.
However, quadratic functions grow very fast; if a single data point is an outlier (e.g., a corrupted image or a mislabeled sample), the "penalty" for not fitting it becomes massive. To minimize the total error, standard algorithms end up warping the entire dictionary just to accommodate a few "bad apples." While some researchers have tried using $\ell_1$ norms or specific robust functions, these often lead to non-smooth optimization problems that are difficult to solve efficiently.
Methods: Robust Dictionary Learning (RDL)
The proposed framework for Robust Dictionary Learning (RDL) is built on two key pillars:
1. Concave Loss Composition
Instead of the standard squared error, the authors use a loss function $F$ defined as the composition of two functions: $F = g \circ \sqrt{\cdot}$. Here, $g$ is a non-decreasing concave function (like a logarithm). Because $F$ is concave, its slope decreases as the error increases. This mathematically ensures that points with huge residuals (outliers) have a diminishing influence on the final dictionary. In essence, concavity acts as a form of mathematical skepticism: if the model misses a point by a large margin, it assumes the point is an outlier and stops trying to fit it.
2. Majorization-Minimization (MM) and Weighting
To solve the resulting non-convex optimization problem, the authors use a Majorization-Minimization (MM) approach. At each iteration, they approximate the concave loss with a linear "surrogate" function. This transforms the complex robust problem into a sequence of weighted standard dictionary learning problems. Each data point $x_i$ is assigned a weight $s_i$; if a point has a large error, its weight drops, effectively telling the algorithm to ignore it in the next step. This provides a natural mechanism for outlier detection via the weights themselves.
3. Undercomplete Initialization Heuristic
Non-convex problems are sensitive to initialization. The authors suggest an initial phase using an "undercomplete" dictionary (fewer atoms than the data's dimensionality). This forces the model to capture the primary structure of the data first, making outliers stand out more clearly so they can be downweighted before the dictionary is expanded to its full size.
Experimental Results
Synthetic Evaluation
In synthetic tests with 50 outliers, the proposed RDL (using a log-loss) correctly identified 47 out of 50 outliers. In contrast, the standard K-SVD algorithm failed to identify any, as the outliers had already "pulled" the dictionary toward them, reducing their relative residuals.
Real-World Performance: MORPH-II
The researchers evaluated their approach on the MORPH-II dataset, a massive face database containing over 40,000 images, for ethnicity and gender classification. The RDL approach consistently outperformed state-of-the-art methods like K-SVD and Label Consistent K-SVD (LC-KSVD).
As shown in the table above, the undercomplete initialization strategy provides a measurable boost to accuracy, particularly in gender classification, where it reached 85.79% compared to 81.88% for K-SVD.
Conclusion
By replacing quadratic losses with concave compositions and employing an undercomplete initialization strategy, the RDL framework offers a robust alternative to traditional dictionary learning. The method demonstrates superior stability and accuracy in the presence of outliers, making it highly suitable for large-scale, real-world datasets where data corruption and mislabeling are common.
Summary updated