The Flag Median and FlagIRLS

• URL: http://arxiv.org/abs/2203.04437v1
• Date: Tue, 8 Mar 2022 23:06:58 GMT
• Title: The Flag Median and FlagIRLS
• Authors: Nathan Mankovich, Emily King, Chris Peterson, Michael Kirby
• Abstract summary: This work proposes a new subspace prototype, the flag median, and introduces the FlagIRLS algorithm for its calculation. We provide evidence that the flag median is robust to outliers and can be used effectively in algorithms like Linde-Buzo-GreyLBG. We find that using FlagIRLS to compute the flag median converges in $4$ on a synthetic dataset.
• Score: 1.5943398589344562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding prototypes (e.g., mean and median) for a dataset is central to a number of common machine learning algorithms. Subspaces have been shown to provide useful, robust representations for datasets of images, videos and more. Since subspaces correspond to points on a Grassmann manifold, one is led to consider the idea of a subspace prototype for a Grassmann-valued dataset. While a number of different subspace prototypes have been described, the calculation of some of these prototypes has proven to be computationally expensive while other prototypes are affected by outliers and produce highly imperfect clustering on noisy data. This work proposes a new subspace prototype, the flag median, and introduces the FlagIRLS algorithm for its calculation. We provide evidence that the flag median is robust to outliers and can be used effectively in algorithms like Linde-Buzo-Grey (LBG) to produce improved clusterings on Grassmannians. Numerical experiments include a synthetic dataset, the MNIST handwritten digits dataset, the Mind's Eye video dataset and the UCF YouTube action dataset. The flag median is compared the other leading algorithms for computing prototypes on the Grassmannian, namely, the $\ell_2$-median and to the flag mean. We find that using FlagIRLS to compute the flag median converges in $4$ iterations on a synthetic dataset. We also see that Grassmannian LBG with a codebook size of $20$ and using the flag median produces at least a $10\%$ improvement in cluster purity over Grassmannian LBG using the flag mean or $\ell_2$-median on the Mind's Eye dataset.

Related papers

• G-Mapper: Learning a Cover in the Mapper Construction [0.7528462379265576]
  The Mapper algorithm is a visualization technique in topological data analysis (TDA) that outputs a graph reflecting the structure of a given dataset. We present an algorithm that optimize the cover of a Mapper graph by splitting a cover repeatedly according to a statistical test for normality. Our algorithm is based on G-means clustering which searches for the optimal number of clusters in $k$-means by iteratively applying the Anderson-Darling test.
  arXiv  Detail & Related papers  (2023-09-12T22:51:16Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Chordal Averaging on Flag Manifolds and Its Applications [22.357999963733302]
  This paper presents a new, provably-convergent algorithm for computing the flag-mean and flag-median of a set of points on a flag manifold under the chordal metric.
  arXiv  Detail & Related papers  (2023-03-23T17:57:28Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Large-Margin Representation Learning for Texture Classification [67.94823375350433]
  This paper presents a novel approach combining convolutional layers (CLs) and large-margin metric learning for training supervised models on small datasets for texture classification. The experimental results on texture and histopathologic image datasets have shown that the proposed approach achieves competitive accuracy with lower computational cost and faster convergence when compared to equivalent CNNs.
  arXiv  Detail & Related papers  (2022-06-17T04:07:45Z)
• Towards Meta-learned Algorithm Selection using Implicit Fidelity Information [13.750624267664156]
  IMFAS produces informative landmarks, easily enriched by arbitrary meta-features at a low computational cost. We show it is able to beat Successive Halving with at most half the fidelity sequence during test time.
  arXiv  Detail & Related papers  (2022-06-07T09:14:24Z)
• Rethinking Semantic Segmentation: A Prototype View [126.59244185849838]
  We present a nonparametric semantic segmentation model based on non-learnable prototypes. Our framework yields compelling results over several datasets. We expect this work will provoke a rethink of the current de facto semantic segmentation model design.
  arXiv  Detail & Related papers  (2022-03-28T21:15:32Z)
• Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype Classification [4.176752121302988]
  In this paper, we present CRS, a novel method for selecting a small yet representative subset of objects as a cluster prototype. Memory and computationally efficient selection of representatives is enabled by leveraging the similarity graph representation of each cluster created by the NN-Descent algorithm. CRS can be used in an arbitrary metric or non-metric space because of the graph-based approach, which requires only a pairwise similarity measure.
  arXiv  Detail & Related papers  (2021-07-03T04:51:07Z)
• Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation [53.95297550117153]
  We propose an end-to-end trainable framework that processes large-scale visual data tensors by looking emphat a fraction of their entries only. The proposed approach is particularly useful for large-scale multidimensional grid data, and for tasks that require context over a large receptive field.
  arXiv  Detail & Related papers  (2021-05-29T08:39:57Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies. We present a number of applications where the use of multiple geometric models improves accuracy. These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
  arXiv  Detail & Related papers  (2021-03-25T14:35:07Z)
• The flag manifold as a tool for analyzing and comparing data sets [4.864283334686195]
  The shape and orientation of data clouds reflect variability in observations that can confound pattern recognition systems. We show how nested subspace methods, utilizing flag manifold, can help to deal with such additional confounding factors.
  arXiv  Detail & Related papers  (2020-06-24T22:29:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.