Source-linked AI summary
Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
Mehrtash Harandi, Conrad Sanderson, Chunhua Shen, Brian C. Lovell
TL;DR
Sparse dictionary learning is difficult when data are linear subspaces on non-Euclidean Grassmann manifolds. The paper embeds these manifolds into symmetric matrices, derives atom-wise updates and a kernelised variant, and reports improved discrimination accuracy across several classification tasks.
Problem
Sparse coding and dictionary learning for subspace-valued data are difficult because Grassmann manifolds are non-Euclidean and lack ordinary vector-space operations.
Method
The paper uses an isometric embedding of Grassmann manifolds into symmetric matrices, derives sparse coding and closed-form atom updates, and adds a kernelised variant.
Results
The proposed approaches achieve notable discrimination-accuracy improvements over state-of-the-art methods on face recognition, action recognition, and dynamic texture classification.
Takeaways & Limitations
The methods provide Grassmann dictionary-learning tools for classification tasks involving videos and image sets.
Takeaways & Limitations
Efficiently solving the SVD-based projection problem is acknowledged as beyond the paper, and discriminative dictionary learning remains future work.
Abstract
from arXiv · showhide
Recent advances in computer vision and machine learning suggest that a wide range of problems can be addressed more appropriately by considering non-Euclidean geometry. In this paper we explore sparse dictionary learning over the space of linear subspaces, which form Riemannian structures known as Grassmann manifolds. To this end, we propose to embed Grassmann manifolds into the space of symmetric matrices by an isometric mapping, which enables us to devise a closed-form solution for updating a Grassmann dictionary, atom by atom. Furthermore, to handle non-linearity in data, we propose a kernelised version of the dictionary learning algorithm. Experiments on several classification tasks (face recognition, action recognition, dynamic texture classification) show that the proposed approach achieves considerable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as kernelised Affine Hull Method and graph-embedding Grassmann discriminant analysis.
1. Introduction
The paper extends sparse dictionary learning to linear subspaces on Grassmann manifolds, where non-Euclidean geometry complicates analysis and optimization. It proposes extrinsic and kernelised methods and evaluates them across several classification tasks.
- Linear subspaces support applications including video and image-set matching, dynamical modeling, noise filtering, biometrics, and domain adaptation.
- Grassmann-manifold geometry makes sparse coding and dictionary learning challenging for subspace-valued signals.
- The paper generalises vector-based sparse coding to subspaces, motivated by sparse approximation of images, videos, and image sets.
- Prior work on sparse coding and dictionary learning in non-Euclidean geometry is limited, with no specialised solution for Grassmann manifolds identified by the authors.
- The proposed approach embeds Grassmann manifolds into symmetric matrices, supports sparse coding, and provides atom-by-atom dictionary updates.
- The kernelised method addresses nonlinear data, while experiments cover face recognition, action recognition, and dynamic texture classification.
2. Background
The background defines Grassmann manifolds as spaces of linear subspaces and explains why Euclidean dictionary-learning formulations do not transfer directly. Non-closure under ordinary arithmetic and non-convexity motivate an extrinsic reformulation.
- Grassmann geometry: A Grassmann manifold G(p,d) is the set of all p-dimensional linear subspaces of R^d, represented through equivalent orthonormal bases.
- Grassmann geometry: Its Riemannian structure provides metrics and geodesic distances between subspaces, with principal angles characterising their relative orientation.
- Euclidean dictionary learning: Euclidean dictionary learning alternates between sparse-code and dictionary updates, each convex when the other variable is fixed.
- Grassmann dictionary learning: The resulting Grassmann dictionary-learning objective is difficult because its operators must be defined appropriately and its geodesic-distance cost is non-convex.
- Grassmann dictionary learning: Grassmann manifolds are not closed under ordinary matrix subtraction and addition, so vector-space dictionary operations require manifold replacements.
3. Grassmann Dictionary Learning (GDL)
GDL embeds Grassmann points into symmetric matrices, preserving projection distance and enabling extrinsic sparse coding with atom-wise dictionary updates. The resulting formulation is convex for sparse codes and admits an eigenvector-based closed-form atom update.
- Embedding and metric: The mapping Π(X)=XXT embeds Grassmann manifolds into symmetric matrices and forms an isometry under projection distance.The paper uses this geometry-preserving representation to work with matrix operations in the induced space.
- Embedding and metric: Matrix addition and subtraction in the induced symmetric-matrix space make the dictionary-learning objective tractable.The projection mapping is identified as the key design choice behind the efficient approach.
- Sparse coding: With a fixed dictionary, sparse coding becomes a convex quadratic problem because the dictionary similarity matrix is positive semidefinite.The formulation uses similarities between signals and dictionary atoms without requiring explicit manifold embedding for sparse-code computation.
- Dictionary update: The dictionary is updated atom by atom by fixing sparse codes and solving independent sub-minimisation problems under orthogonality constraints.This follows the standard alternating strategy: sparse codes and dictionary atoms are optimized in separate steps.
- Dictionary update: The constrained atom-update solution is obtained from an eigenvalue problem, using p eigenvectors of a matrix S.Lagrange multipliers convert the update into an eigenvector computation.
4. Kernelised GDL
KGDL extends Grassmann dictionary learning with a kernel formulation for complex nonlinear structures. It represents subspaces in a Hilbert space through kernel matrices while retaining convex sparse coding and atom-wise dictionary updates.
- Kernel extension: KGDL is introduced to model complex nonlinear structures in the original data.The kernel extension is presented as the nonlinear counterpart of the GDL method.
- Kernel representation: A kernel function maps input samples into a dot-product Hilbert space, where subspaces are represented from mapped samples.The induced inner products are computed through the kernel function k(·,·).
- Kernel representation: Kernel subspace inner products are computed as AZ^T K(Z,W) AW using kernel matrices between sample sets.The coefficient matrices for input sets come from KPCA, whereas dictionary-atom coefficients are learned by KGDL.
- Optimization: Sparse-code computation remains convex, and the dictionary is updated atom by atom with sparse codes fixed.The kernelized procedure preserves the alternating optimization structure of linear GDL.
- Optimization: The KGDL atom update represents each dictionary atom through a linear combination of training samples and solves a generalized eigenvalue problem.The representer theorem reduces the atom representation, while the update uses SΨv = λK(Dr,Dr)v.
5. Further Discussion
The extrinsic formulation permits sparse reconstructions in the symmetric-matrix space, even when their linear combinations are not themselves Grassmann points. An intrinsic alternative projects reconstructions back to the Grassmann manifold, but its SVD-based optimization is acknowledged as difficult.
- Extrinsic versus intrinsic coding: Extrinsic sparse coding does not require the reconstructed linear combination to lie on the Grassmann manifold.The method treats Π(X) as a mapping and permits the reconstruction to remain in the ambient symmetric-matrix space.
- Extrinsic versus intrinsic coding: Eckart–Young projection can convert a symmetric-matrix combination into a nearby Grassmann point by retaining rank p and equalizing singular values.The projected matrix is selected as the closest rank-p matrix in Frobenius norm.
- Extrinsic versus intrinsic coding: Over-complete dictionaries are expected to approximate XXT with reconstructions closely tied to Grassmannian points.Grassmann points correspond to rank-p, symmetric, idempotent matrices in the embedded representation.
- Intrinsic formulation: The intrinsic formulation enforces Grassmann structure with a projection operator that imposes idempotency and rank constraints.This projection can be computed with SVD.
- Intrinsic formulation: Efficiently solving the intrinsic formulation remains beyond the paper because repeated SVD involvement makes optimization tedious and challenging in vision applications.The authors identify efficient alternatives as an open direction.
6. Experiments
The experiments evaluate GDL and KGDL against established methods on face recognition, dynamic texture classification, and action recognition using image sets represented as Grassmann subspaces. Across the reported tasks, the proposed methods achieve strong classification performance, including the highest reported DynTex++ result and roughly a ten-point Ballet advantage for KGDL over GGDA.
- Experimental setup: The evaluation compares GDL and KGDL with DCC, KAHM, GDA, and GGDA on face, dynamic-texture, and action-recognition tasks.The methods generate sparse codes that are then supplied to an SVM for classification.
- Face recognition: YouTube celebrity videos were converted into 1,471 image sets, represented by order-5 subspaces, with ten random train-test splits averaged.Faces were detected, resized to 96×96, described using LBP, and split into 1,236 training and 235 testing points.
- Action recognition: Both GDL and KGDL outperform DCC, KAHM, GDA, and KGDA on Ballet, while KGDL exceeds the closest competitor, GGDA, by roughly ten percentage points.The Ballet dataset contains 44 videos covering eight complex actions with substantial intra-class variation.
- Initialization analysis: On one YouTube split, GDL achieved 72.21% mean accuracy across ten initializations, while selecting the minimum-reconstruction-error dictionary yielded 73.19%.The reported standard deviation across random initializations was 1.6.
- Intrinsic comparison: The intrinsic approach required 26706s versus 955sec for the proposed algorithm and achieved 68.51% versus 70.47% accuracy on the reported YouTube experiment.The authors conjecture that the intrinsic method’s affine constraint may explain this counter-intuitive performance difference.
7. Main Findings and Future Directions
The paper’s extrinsic and kernelised Grassmann dictionary methods improve discrimination accuracy across several classification tasks. The reconstruction-focused dictionary remains limited when labelled data are available, motivating discriminative extensions.
- The method embeds Grassmann manifolds into symmetric matrices, derives sparse codes, and updates dictionary atoms in closed form.
- A kernelised version addresses non-linearity in the data.
- The proposed approach achieves notable discrimination-accuracy improvements over state-of-the-art methods across face, action, and dynamic-texture classification.
- The dictionary minimises reconstruction error, which is not necessarily optimal when labelled data are available.
- The authors identify discriminative penalty terms, richer Bregman-divergence costs, and rank-deficiency constraints as directions for further work.
Appendix
The appendix establishes how metric relationships transfer to intrinsic curve lengths on metric spaces. It uses this result to support the geometric analysis underlying the proposed methods.
- If two metrics induce identical intrinsic metrics up to scale, every curve has the same length under them up to that scale.
- Uniform equality of two metrics implies equality of their intrinsic metrics.
- The appendix then examines the local behaviour of the relevant metric expressions.