Source-linked AI summary
Sparse Coding and Dictionary Learning for Symmetric Positive Definite Matrices: A Kernel Approach
Mehrtash T. Harandi, Conrad Sanderson, Richard Hartley, Brian C. Lovell
TL;DR
Sparse coding and dictionary learning on SPD matrices are challenging because their Riemannian geometry is non-Euclidean and computationally burdensome. The paper uses the Stein kernel to embed SPD manifolds into RKHS, producing a convex kernelized Lasso and a Stein-kernel-based dictionary learner. Across face recognition, texture classification, and person re-identification, the sparse coding approach improves discrimination accuracy over state-of-the-art methods and is faster than the MAXDET tensor-sparse-coding reformulation.
Problem
The paper addresses sparse coding within SPD matrices, where Riemannian geometry has received comparatively little attention and basic computations are nonlinear and numerically burdensome.
Method
The method embeds SPD manifolds into RKHS using the Stein kernel, yielding a convex kernelized Lasso and a Stein-kernel-based Riemannian dictionary-learning algorithm.
Results
Experiments on face recognition, texture classification, and person re-identification show notable discrimination-accuracy improvements over state-of-the-art methods.
Takeaways & Limitations
The approach is also considerably faster than the MAXDET reformulation used by Tensor Sparse Coding, while learned dictionaries improve representation error and classification accuracy over Riemannian k-means.
Abstract
from arXiv · showhide
Recent advances suggest that a wide range of computer vision problems can be addressed more appropriately by considering non-Euclidean geometry. This paper tackles the problem of sparse coding and dictionary learning in the space of symmetric positive definite matrices, which form a Riemannian manifold. With the aid of the recently introduced Stein kernel (related to a symmetric version of Bregman matrix divergence), we propose to perform sparse coding by embedding Riemannian manifolds into reproducing kernel Hilbert spaces. This leads to a convex and kernel version of the Lasso problem, which can be solved efficiently. We furthermore propose an algorithm for learning a Riemannian dictionary (used for sparse coding), closely tied to the Stein kernel. Experiments on several classification tasks (face recognition, texture classification, person re-identification) show that the proposed sparse coding approach achieves notable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as tensor sparse coding, Riemannian locality preserving projection, and symmetry-driven accumulation of local features.
1 Introduction
The paper addresses sparse coding for SPD matrices, whose Riemannian geometry is useful but difficult to handle computationally. It uses RKHS embedding and the Stein kernel to obtain efficient sparse coding and dictionary learning, with improved classification performance.
- SPD matrices support compact covariance descriptors used across computer vision and machine learning applications.
- Riemannian geometry better suits SPD matrices than Euclidean analysis, but its nonlinear similarities and distances complicate optimization and increase numerical burden.
- The paper embeds SPD-manifold data into RKHS instead of directly embedding it into Euclidean spaces.
- The Stein-kernel embedding yields a convex, kernelized Lasso solver and supports sparsity-maximizing dictionary learning for SPD matrices.
- The proposed sparse coding approach outperforms tensor, log-Euclidean, Gabor, and Riemannian locality-preserving alternatives across several visual classification tasks.
2 Background
The background develops Stein divergence and its kernel as geometry-aware tools for SPD manifolds. Their relationship to geodesic structure motivates kernel methods while enabling positive-definite similarity representations.
- The paper introduces symmetric Stein divergence as a symmetrized Bregman matrix divergence and uses it to construct the Stein kernel.
- Stein divergence follows geodesic curves similarly to Riemannian distance, although with a weaker inequality.
- The Stein–Riemannian relationship provides motivation for addressing Riemannian problems through the divergence.
- A Riemannian kernel is a symmetric function satisfying a nonnegative quadratic-form condition over finite SPD sets.
- Under a condition on its parameter, the Stein kernel produces a positive-definite kernel matrix and can be computed efficiently using Cholesky decomposition.
3 Kernel Sparse Coding
Kernel sparse coding represents an SPD query as a sparse linear combination of dictionary atoms after RKHS embedding. The resulting Lasso problem is convex, and sparse codes support direct or classifier-based recognition.
- The method represents an SPD query point sparsely over RKHS images of Riemannian dictionary atoms.
- The kernelized Lasso uses query–dictionary and dictionary–dictionary kernel matrices, making the optimization convex and similar to Euclidean sparse coding.
- 3.1 Classification Using Sparse Codes: When dictionary atoms carry class labels, class-specific codes support residual-based classification for closed-set identification.
- 3.1 Classification Using Sparse Codes: When dictionary atoms are unlabeled, sparse codes become feature vectors for Euclidean classifiers such as SVMs in closed-set and open-set tasks.
4 Learning Riemannian Dictionaries
Riemannian dictionary learning alternates sparse coding with independent atom updates while keeping the Stein-kernel formulation. The update lacks a closed form, so previous kernel and inverse values are exploited iteratively.
- The dictionary-learning objective jointly minimizes energy over SPD dictionary atoms and sparse codes.
- The algorithm alternates between computing sparse codes with a fixed dictionary and updating dictionary atoms with fixed codes.
- Each dictionary atom is updated independently after initialization, such as through Riemannian clustering using the Karcher mean.
- Because atom updates contain linear and nonlinear inverse and kernel terms, they do not admit a closed-form root solution.
- Previous kernel and inverse values are reused during updates, and atoms are normalized each iteration to avoid numerical degeneracy.
5 Experiments
Experiments evaluate RSR on synthetic classification, face recognition, texture classification, and person re-identification, with and without learned dictionaries. RSR generally achieves the strongest accuracy, while dictionary learning reduces RKHS representation error and RSR is faster than TSC.
- Experimental setup: RSR was evaluated without dictionary learning on closed-set synthetic, face, texture, and person re-identification tasks using residual-error classification.Each dictionary atom was a training sample, enabling comparison with prior state-of-the-art methods.
- Synthetic Data: RSR achieved superior synthetic-data recognition accuracy and was substantially faster than Tensor Sparse Coding.The synthetic experiments used 512 samples from four classes, repeated over 100 generated datasets.
- Face Recognition: RSR obtained the highest face-recognition accuracy across the evaluated pose tests and significantly outperformed Euclidean methods on non-frontal ‘bg’ images.Compared methods included PCA-SRC, GSR, logE-SR, and TSC.
- Texture Classification: RSR achieved the highest texture-recognition accuracy in every scenario except ‘5c’, where Tensor Sparse Coding performed slightly better.The comparison used logE-SR and TSC across nine Brodatz test scenarios.
- Person Re-identification: RSR obtained the highest accuracy on ETHZ Sequences 1 and 2, while Sequence 3 showed very similar performance among RSR, SDALF, and RLPP.Performance was measured with cumulative matching characteristic curves.
- Dictionary Learning: The proposed dictionary-learning algorithm produced lower RKHS representation error than Riemannian k-means during synthetic-data iterations.Learned dictionaries were compared using representation error defined by Eqn. (10).
6 Main Findings and Future Directions
The paper addresses sparse representation on Riemannian manifolds using the Stein kernel and extends this framework to dictionary learning for SPD matrices. Experiments report improved classification performance, faster sparse coding than MAXDET-based tensor sparse coding, and several future directions.
- The Stein-kernel approach embeds Riemannian manifolds into RKHS, yielding a relaxed and extended Lasso formulation for sparse representation.
- The proposed sparse coding method improves discrimination accuracy across face recognition, texture classification, and person re-identification tasks.
- The method is considerably faster than the MAXDET reformulation used by Tensor Sparse Coding.
- The learned Riemannian dictionary achieves lower RKHS representation error and improved classification accuracy compared with Riemannian k-means.
- Future work includes large-margin classification on SPD matrices using Stein divergence, extending support vector machines to tensor spaces.