Research map / Learning theory and algorithms / Clustering
A Flag Decomposition for Hierarchical Datasets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Flag Decomposition (FD), a QR-like factorization that maps hierarchical real-valued data to a hierarchy-preserving flag in Stiefel coordinates, computed by a block Gram-Schmidt algorithm (Flag-BMGS) with robust IRLS-SVD variant, and applies it to denoising, clustering, and few-shot learning.
Problem
Standard decompositions such as SVD and QR flatten hierarchical data and cannot recover the full hierarchy-preserving flag from data with complex column hierarchies, which limits flag-based analysis in vision and ML.
Approach
Defines a flag decomposition D = QRP^T for data with a column hierarchy, computed by Flag-BMGS (block modified Gram-Schmidt with per-block subspace solves via SVD, or IRLS-SVD for robustness), which preserves nested subspaces that SVD and QR cannot recover jointly.
Key results
- On simulated data FD and RFD improve flag recovery over SVD under additive noise and outliers, with RFD giving the most accurate flag recovery under outliers (Fig. 5-6).
- On hyperspectral denoising FD consistently improves SNR/LRSE over SVD for Gaussian noise on KSC and Indian Pines (Fig. 8).
- In few-shot 5-way classification, the flag classifier performs similarly to subspace classifiers and improves accuracy in two cases, e.g. Flowers102 5-shot 93.2 vs 91.4 Euclidean.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · EuroSat, 3 shots, 5 ways | classification accuracy: 76.7 -> 77.7 | Helped |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · EuroSat, 3 shots, 5 ways | classification accuracy: 77.6 -> 77.7 | No clear effect |
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · CIFAR-10, 3 shots, 5 ways | classification accuracy: 58.6 -> 59.6 | Helped |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · CIFAR-10, 3 shots, 5 ways | classification accuracy: 59.6 -> 59.6 | No clear effect |
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · Flowers102, 3 shots, 5 ways | classification accuracy: 88.2 -> 90.2 | Helped |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · Flowers102, 3 shots, 5 ways | classification accuracy: 90.2 -> 90.2 | No clear effect |
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · EuroSat, 5 shots, 5 ways | classification accuracy: 80.7 -> 81.8 | Helped |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · EuroSat, 5 shots, 5 ways | classification accuracy: 81.8 -> 81.8 | No clear effect |
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · CIFAR-10, 5 shots, 5 ways | classification accuracy: 65.2 -> 65.2 | No clear effect |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · CIFAR-10, 5 shots, 5 ways | classification accuracy: 65.2 -> 65.2 | No clear effect |
| Use flag prototypes instead of Euclidean prototypes | Few-shot classifier with AlexNet · Flowers102, 5 shots, 5 ways | classification accuracy: 91.4 -> 93.2 | Helped |
| Use flag prototypes instead of subspace prototypes | Few-shot classifier with AlexNet · Flowers102, 5 shots, 5 ways | classification accuracy: 93.2 -> 93.2 | No clear effect |
Surprising findings
- For exponential and uniform noise in hyperspectral denoising, FD and SVD produce similar quality denoising.
Limitations
- Flag-BMGS is prone to Gram-Schmidt instabilities and requires the flag type and column hierarchy as inputs.
- Flag type selection relies on heuristic singular value truncation rather than automatic detection.
- Few-shot flag classifier is not fine-tuned end-to-end and gains over baselines are small or absent in most settings.
Experimental setup
Datasets: KSC hyperspectral dataset Indian Pines hyperspectral dataset YFB EuroSat CIFAR-10 Flowers102 ImageNet
Benchmarks: KSC Indian Pines EuroSat CIFAR-10 Flowers102 YFB
Metrics: chordal distance LRSE SNR clustering accuracy classification accuracy
Baselines: SVD QR IRLS-SVD Euclidean (prototypical networks) subspace classifier (adaptive subspace networks)
Builds on: Block Modified Gram-Schmidt Optimization on flag manifolds (Ye et al.) Adaptive subspace networks Prototypical networks
Closest papers by meaning
- Fun with Flags: Robust Principal Directions via Flag Manifolds (CVPR 2024 · similarity 0.90)
- The Flag Median and FlagIRLS (CVPR 2022 · similarity 0.87)
- Learning Eigenstructures of Unstructured Data Manifolds (CVPR 2026 · similarity 0.85)
- Geometric Analysis of Nonlinear Manifold Clustering (NeurIPS 2024 · similarity 0.84)
- StelLA: Subspace Learning in Low-rank Adaptation using Stiefel Manifold (NeurIPS 2025 · similarity 0.84)
- Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.