Abstract
In the past decade, Grassmann manifolds (Grassmannian) have been commonly used in mathematical formulations of many Computer Vision tasks. Averaging points on a Grassmann manifold is a very common operation in many applications including but not limited to, tracking, action recognition, video-face recognition, face recognition, etc. Computing the intrinsic/Fréchet mean (FM) of a set of points on the Grassmann can be cast as finding the global optimum (if it exists) of the sum of squared geodesic distances cost function. A common approach to solve this problem involves the use of the gradient descent method. An alternative way to compute the FM is to develop a recursive/inductive definition that does not involve optimizing the aforementioned cost function. In this paper, we propose one such computationally efficient algorithm called the Grassmann inductive Fréchet mean estimator (GiFME). In developing the recursive solution to find the FM of the given set of points, GiFME exploits the fact that there is a closed form solution to find the FM of two points on the Grassmann. In the limit as the number of samples tends to infinity, we prove that GiFME converges to the FM (this is called the weak consistency result on the Grassmann manifold). Further, for the finite sample case, in the limit as the number of sample paths (trials) goes to infinity, we show that GiFME converges to the finite sample FM. Moreover, we present a bound on the geodesic distance between the estimate from GiFME and the true FM. We present several experiments on synthetic and real data sets to demonstrate the performance of GiFME in comparison to the gradient descent based (batch mode) technique. Our goal in these applications is to demonstrate the computational advantage and achieve comparable accuracy to the state-of-the-art.
Introduction
In many computer vision applications, data is naturally represented as linear subspaces, which correspond to points on a Grassmann manifold. For instance, a collection of face images under varying illumination or a video sequence of a specific action can be modeled as a subspace. A fundamental operation in analyzing such data is finding the "average" point, known as the Fréchet Mean (FM).
Traditionally, the FM is computed by minimizing the sum of squared geodesic distances between the mean and all points in the dataset. This optimization is typically performed using iterative gradient descent (batch mode), which is computationally intensive. As datasets grow in size and the demand for real-time processing increases, these traditional methods become a bottleneck. This paper introduces the Grassmann Inductive Fréchet Mean Estimator (GiFME), a recursive alternative that offers significant computational advantages.
Methodology: The GiFME Algorithm
GiFME shifts the computation from a global batch optimization to an incremental, recursive process. Instead of processing all data points simultaneously, the algorithm updates the mean estimate as each new sample arrives:
- Initialization: The first data point is taken as the initial mean estimate.
- Recursive Update: Upon the arrival of the $(k+1)$-th point, the new mean is calculated by moving along the geodesic (the shortest path on the manifold) between the current estimate and the new point.
- Weighting: The step size along this geodesic is defined by a weight $\omega_{k+1} = 1/(k+1)$, effectively maintaining a running average on the manifold.
The efficiency of GiFME stems from the existence of a closed-form solution for geodesics on the Grassmannian, involving Singular Value Decomposition (SVD). This allows the algorithm to bypass the expensive iterative exponential and logarithmic map computations required by gradient descent.
Furthermore, the authors provide a rigorous proof of Weak Consistency. By mapping the Grassmannian geometry to a hypersphere, they demonstrate that as the number of samples $N \to \infty$, the recursive estimate converges in probability to the true Fréchet Mean.
Experimental Evaluation
Computational Efficiency
The primary advantage of GiFME is its scalability. In synthetic tests involving 1,000 samples, the time taken by the traditional batch method (GFME) grows significantly with the number of samples, whereas GiFME maintains a near-constant update time per sample.
Real-World Performance
The algorithm was tested on standard computer vision benchmarks, including the YaleExtendedB face database and the KTH Action Database.
On the YaleExtendedB dataset, which contains over 16,000 images, GiFME achieved a staggering speedup. While the batch method required over 6,800 seconds to compute the mean, GiFME completed the task in just over 16 seconds—a 400x improvement—while maintaining nearly identical precision.
Similar results were observed in the KTH Action Database across various scenarios (d1-d4). For example, in scenario d1, GiFME reduced the computation time from 2714.71 seconds to 6.55 seconds, with only a marginal difference in precision (81.36% vs 83.24%).
Discussion and Conclusion
GiFME demonstrates that for Grassmann manifolds, a recursive approach is not only theoretically sound but practically superior for large-scale computer vision tasks. By replacing global optimization with a series of closed-form updates, the method achieves massive speedups without sacrificing accuracy.
However, some constraints remain. The convergence proof assumes data localization (within a geodesic ball of radius $<\pi/4$). In cases where data is widely dispersed, the order of sample processing may influence the final estimate for finite samples. Future work may involve extending this recursive framework to other manifolds, such as the Stiefel manifold, to further broaden its applicability in geometric data analysis.
Summary updated